山东省第七届省赛

A:水

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T,A,B;
    while(~scanf("%d",&T)){
        for(int i=0;i<T;++i){
            cin>>A>>B;
            if(A%B){
                cout<<(A/B)+1<<endl;
            }else{
                cout<<(A/B)<<endl;
            }
        }
    }
    return 0;
}

B:二分(或者可以暴力,只有45个FB)结论题,用到斐波那契博弈里的一个结论:任何数都可以被拆成不同斐波那契的和,进而猜测直接从最大的小于N的FB往下找即可

我吐槽下SDUT的OJ…尼玛10^9能写成109,劳资找了大大大大大大半天错硬是不知道错哪里了艹

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
int Fb[maxn],M;
int vis[maxn],has_ans;

void init(){
    Fb[0]=1;
    Fb[1]=2;
    for(int i=2;i<maxn;++i){
        Fb[i]=Fb[i-1]+Fb[i-2];
        //printf("%d\n",Fb[i]);
    }

}

void solve(int N){
    stack<int> ans;
    int mx=maxn;
    while(N!=0){
        int ind=lower_bound(Fb,Fb+mx,N)-Fb;
        if(Fb[ind]>N)ind-=1;
        N=N-Fb[ind];
        ans.push(Fb[ind]);
    }
    printf("%d=",M);
    int t=0;
    while(!ans.empty()){
        if(!t){
            printf("%d",ans.top());t++;
        }else printf("+%d",ans.top());
        ans.pop();
    }
    printf("\n");
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        has_ans=0;
        scanf("%d",&M);
        solve(M);
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 40ms
Take Memory: 196KB
Submit time: 2018-03-04 13:39:50
****************************************************/

E:简单枚举

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;

int T,N,M;
char mp[maxn][maxn];
int dist[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

bool check(int x,int y){
    if(x<1 || x>M || y<1 || y>N) return false;
    return true;
}

int main(){
    scanf("%d",&T);
    while(T--){
        int ans=0;
        scanf("%d%d",&M,&N);
        for(int i=1;i<=M;++i){
            scanf("%s",mp[i]+1);
        }
        for(int i=1;i<=M;++i){
            for(int j=1;j<=N;++j){
                if(mp[i][j]=='#'){
                    for(int k=0;k<4;++k){
                        int x=i+dist[k][0],y=j+dist[k][1];
                        if(check(x,y)){
                            if(mp[x][y]=='#')continue;
                            int room=0;
                            for(int kk=0;kk<4;++kk){
                                int xx=x+dist[kk][0],yy=y+dist[kk][1];
                                if(check(xx,yy)){
                                    if(mp[xx][yy]=='#')++room;
                                }
                            }
                            if(room==1)ans++;
                        }else ++ans;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 228ms
Take Memory: 212KB
Submit time: 2018-03-04 14:46:06
****************************************************/

G:找规律,不像博弈,抱歉,会打表,但是规律想不出来,对不起

打表

#include<bits/stdc++.h>
using namespace std;

int solve(int N){
    int ans=0;
    for(int i=1;i<N;++i){
        for(int j=i;j<N-i;++j){
            int k=N-i-j;
            if((i^j^k)==0) ans++;
        }
    }
    return ans;
}

int main(){
    for(int i=1;i<=200;++i){
        printf("%d: %d\n",i,solve(i)/3);
    }
    return 0;
}

找的规律,知道规律了,直接粘的别人代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans,pp;
    int i;
    long long int f[100];
    f[2]=1;
    f[1]=0;
    f[0]=0;
    for(i=3;i<30;i++)
        f[i]=f[i-1]*3+1;
    long long int a;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>a;
        ans=0;
        if(a%2)
        {
            cout<<0<<endl;
            continue;
        }
        while(a!=0)
        {
            pp=a%2;
            if(pp)
                ans++;
            a/=2;
        }
        cout<<f[ans]<<endl;
    }
}

J:题目翻译: http://www.bubuko.com/infodetail-1612259.html 说实话,完全理解题意了基本就是水题.但对我不是.

#include<bits/stdc++.h>
using namespace std;
int T;
char str[1000];
int main(){
    cin>>T;
    while(T--){
        int N,M;
        cin>>N>>M;
        int c=0,m=0,o=0,b=0;
        getchar();
        for(int i=0;i<N;++i){
            gets(str);
            if(str[0]=='C'){
                c++;
            }else if(str[0]=='M'){
                m++;
            }else if(str[0]=='O'){
                o++;
            }else if(str[0]=='B'){
                b++;
            }
        }
        int ans=o*(2+(N-1)+m*2)+b*(2+m*2);
        if(ans>=M){
            puts("Mrghllghghllghg!");
        }else puts("Tell you a joke, the execution of Paladin.");
    }
    return 0;
}

K:水

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010,maxm=5010;
int N;
stack<char> st;
int main(){
    while(~scanf("%d\n",&N)){
        char qb;
        while(N--){
            int f=0;
            do{
                do{
                    qb=getchar();
                    if(isalpha(qb)) st.push(qb);
                }while(qb!=' ' && qb!='\n');
                if(f==0)f++;
                else printf(" ");
                while(!st.empty()){
                    printf("%c",st.top());
                    st.pop();
                }
            }while(qb!='\n');
            printf("\n");
        }
    }
    return 0;
}

第七届山东省ACM/ICPC K Reversed Words

【Tip】

我太菜辣,没有1A  ……F**k

【Code】

#include<bits/stdc++.h>
using namespace std;
char str[10000];
int main(){
    int T;
    scanf(“%d\n”,&T);
    while(T–){
        int star=-1;
        gets(str);
        int len=strlen(str);
        for(int i=0;i<len+1;++i){
            if(str[i]==’ ‘ || str[i]==’\0′ || str[i]==’\n’){
                for(int j=i-1;j>star;–j)
                    putchar(str[j]);
                star=i;
                if(str[i]==’ ‘)putchar(str[i]);
            }
        }
        putchar(‘\n’);
    }
    return 0;
}

第七届山东省ACM/ICPC H Memory Leak

【类型】

模拟,感受一下什么叫绝望吧…

【Tip】

F**k!…..QNMD鲁棒性….QAQ

后记…发现自己的代码可以过…但是忘了关freopean..所以才WA…尴尬//= // =//

【Code】

鲁棒形比我好,一点的,代码.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
 //   #ifndef DEF
 //    freopen(“in.txt”,”r”,stdin);
 //    freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[100],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    while(scanf(“%s”,def)){
                        int flag=1,star_num=0,ind_num=0,len=strlen(def);
                        for(int i=0;i<len;++i){
                            if(flag==1 && def[i]!='[‘){
                                S[num].s[star_num++]=def[i];
                            }
                            if(def[i]=='[‘){
                                S[num].s[star_num]=0;
                                flag=2;
                                continue;
                            }
                            if(flag==2 && def[i]!=’]’){
                                ind_num=ind_num*10+(def[i]-‘0’);
                            }
                            if(def[i]==’]’){
                                S[num].contain[0]=0;//初始化
                                S[num].has_end=true;
                                S[num].ind=ind_num;
                                star_num=0;
                                ind_num=0;
                                num++;
                                continue;
                            }
                        }
                        if(def[len-1]==’;’) break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(“%s”,name);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

我的代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num=0;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
//   #ifndef DEF  //<-F**k U
  //   freopen(“in.txt”,”r”,stdin);
  //   freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[10],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                scanf(” “);
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    int flag=1,star_num=0,ind_num=0;
                    gets(def);
                    for(int i=0,start=0;def[i]!=’\0′;++i){
                        if(def[i]==’ ‘ || def[i]==’,’) continue;
                        if(flag==1 && def[i]!='[‘){
                            S[num].s[star_num++]=def[i];
                        }else if(def[i]=='[‘){
                            S[num].s[star_num]=0;
                            flag=2;
                        }else if(flag==2 && def[i]!=’]’){
                            ind_num=ind_num*10+(def[i]-‘0’);
                        }else if(def[i]==’]’){
                            S[num].contain[0]=0;//初始化
                            S[num].has_end=true;
                            S[num].ind=ind_num;
                            star_num=0;
                            ind_num=0;
                            num++;
                            flag=1;
                        }else if(def[i]==’;’)
                            break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(” “);
                    gets(name);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

第七届山东省ACM/ICPC F Feed the monkey

【类型】

DP

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1761/pid/3565

【题解】

用dp[i][j][k][t]表示剩余i个第一种物品,j个第二种物品,k个第三种物品.以第t种物品为结尾的安排饲养表的种数.

递归的思想来合并所有的情况,不过是减了所有的重复枝.

【Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
const ll mod=1000000007;
const int maxn=55;
ll dp[maxn][maxn][maxn][4];
int N1,N2,N3,D1,D2,D3,T;

int main(){
    while(~SI(T)){
        while(T–){
            cle(dp,0);
            SIII(N1,N2,N3);
            SIII(D1,D2,D3);
            red(i,N1,0) red(j,N2,0) red(k,N3,0){
                rez(s,1,min(i,D1)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i-s][j][k][0]=(dp[i-s][j][k][0]+1)%mod;
                    else
                        dp[i-s][j][k][0]=((dp[i-s][j][k][0]+dp[i][j][k][1])%mod+dp[i][j][k][2])%mod;
                }
                rez(s,1,min(j,D2)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i][j-s][k][1]=(dp[i][j-s][k][1]+1)%mod;
                    else
                        dp[i][j-s][k][1]=((dp[i][j-s][k][1]+dp[i][j][k][0])%mod+dp[i][j][k][2])%mod;
                }
                rez(s,1,min(k,D3)){
                    if(i==N1 && j==N2 && k==N3)
                        dp[i][j][k-s][2]=(dp[i][j][k-s][2]+1)%mod;
                    else
                        dp[i][j][k-s][2]=((dp[i][j][k-s][2]+dp[i][j][k][0])%mod+dp[i][j][k][1])%mod;
                }
            }
            ll ans=0;
            ans=((dp[0][0][0][0]+dp[0][0][0][1])%mod+dp[0][0][0][2])%mod;
            printf(“%lld\n”,ans);
        }
    }
    return 0;
}