7.31

索引

题单

• P1094 纪念品分组【贪心】
• P1181 数列分段Section I【贪心 过水】
• P1803 凌乱的yyy / 线段覆盖

• P1538 迎春舞会之数字舞蹈【恶心模拟】

• P1134 阶乘问题【数论】

## noip原题

- P1134 阶乘问题【数论】

/*
translation:

solution:
    分析:N!的末尾只会是2,4,6,8(在此题中没有0).又[2,4,6,8]中任意一个数乘6,末尾仍是本身.2 * 6 = 12,末尾为2, 4 * 6 =24,
    末尾为4, 6 * 6=36,末尾为6,8 * 6 =48,末尾为8.又末尾数字只受末尾数字影响,如4. 4 * 6得到的末尾数字与4 * 16的末尾数
    字一样.又4 * 10=40,末尾数字为4(此题不要末尾0).则4 * 2 *8==4 * 2 *5(意思是得到的末尾数字是一样的).故所有乘5的时
    候都可以换为乘8.又多次乘8末尾是有规律的.找出规律即可.
trigger:

note:
    *
date:
    2019.07.31
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define mem(a,b) memset(a,b,sizeof(a))

#define N

int n,ans=1;
int a[4]={6,8,4,2};
int main(){
    #ifdef WIN32
    freopen("","r",stdin);
    #endif
    rd(n);
    while(n){
        rep(i,1,n%10)//除了5之外,其他数字原样乘.
        //n%10 的原因:答案只受末尾数字影响
            if(i!=5)
                ans=ans*i%10;//跳过乘5(此时可以放心%10)
        n/=5;//n/5即少乘了多少次5
        //即乘8的次数
        ans=ans*a[n%4]%10;//四次一循环(此时可以放心%10)
    }
    printf("%d",ans);
    return 0;
}

P1803 凌乱的yyy / 线段覆盖

在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。
最左边的线段放什么最好？
显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少
其他线段放置按右端点排序，贪心放置线段，即能放就放

- P1094 纪念品分组

/*
translation:
    他要把购来的纪念品根据价格进行分组，
    但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。
solution:
    第一次交RE了，因为循环结束有两种情况：
        - 情况1：刚好取完最后两个
        - 情况2：取完最后一个，ans++
trigger:

note:
    *贪心，排序
date:
    2019.07.31
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define mem(a,b) memset(a,b,sizeof(a))

#define N 30010

ll w,ans,n;
ll a[N];

int main(){
    #ifdef WIN32
    freopen("fenzu.txt","r",stdin);
    #endif
    rd(w);
    rd(n);
    rep(i,1,n)rd(a[i]);
    sort(a+1,a+n+1);
    ll i=1;
    ll j=n;
    while(1){
        if(a[i]+a[j]<=w){
            ans++;
            a[i]=INT_MAX,a[j]=INT_MAX;
            i++,j--;
        }
        else{
            ans++;
            a[j]=INT_MAX;
            j--;
        }
        if(i==j+1)break;//////////////不要忘了处理情况1
        if(i==j){//情况2
            ans++;
            break;
        }
    }
    printf("%lld",ans);
    return 0;
}
/*
100
9
90
20
20
30
50
60
70
80
90
*/
//6 

P1538 迎春舞会之数字舞蹈

/*
translation:

solution:

trigger:

note:
    *
date:
    2019.07.31
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define dwn(i,a,b) for(ll i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

int k,h,w,r;
char bj[64][8670];
bool a[10][7]={
                {1,1,1,1,1,1,0},
                {0,1,1,0,0,0,0},
                {1,1,0,1,1,0,1},
                {1,1,1,1,0,0,1},
                {0,1,1,0,0,1,1},
                {1,0,1,1,0,1,1},
                {1,0,1,1,1,1,1},
                {1,1,1,0,0,0,0},
                {1,1,1,1,1,1,1},
                {1,1,1,1,0,1,1}
            };

void find(char c){
    if(a[c-'0'][0]) for(int i=r+1;i<r+w-2;i++) bj[0][i]='-';
    if(a[c-'0'][1]) for(int i=1;i<=k;i++) bj[i][r+w-2]='|';
    if(a[c-'0'][2]) for(int i=k+2;i<h-1;i++) bj[i][r+w-2]='|';
    if(a[c-'0'][3]) for(int i=r+1;i<r+w-2;i++) bj[k+k+2][i]='-';
    if(a[c-'0'][4]) for(int i=k+2;i<h-1;i++) bj[i][r]='|';
    if(a[c-'0'][5]) for(int i=1;i<=k;i++) bj[i][r]='|';
    if(a[c-'0'][6]) for(int i=r+1;i<r+w-2;i++) bj[k+1][i]='-';
}

int main() {
    string s;
    rd(k);
    cin>>s;
    h=k*2+3;
    w=k+3;//每个数字的宽度（包含一个空格）
    for(int i=0;i<s.length();i++){
        find(s[i]);
        r+=w;
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<r;j++){
            if(bj[i][j]) putchar(bj[i][j]);
            else putchar(' ');
        }
        putchar('\n');
    }
    return 0;
}