山东省第七届省赛

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;
}

技巧论 QAQ

凡事要讲究技巧,无技不成巧,先将遇到的技巧记录下来..

对的…这特么就是一个远古巨坑

中途相遇法(又称折半枚举,双向搜索)

思想论

如果纬度特别高时,比如数据量为N,总情况数为N^4,全部遍历一遍是肯定不可以的,不过可以将它们折半成AB和CD再考虑,就可以快速解决了.

从两个数列中考虑的话,就只剩下N^2种情况了,因此对两半枚举完以后排一下序,就可以用二分搜索了.

例题:山东第一届省赛 D

右侧标签云中找一下第一节山东省塞即可

爬梯法

尺取法

思想:

规定那个两个点,先固定左端点,如果小于答案,则右端点向右走,否则左端点向左走
POJ 3061

分块法

51nod 1225

倍增算法

康托展开

山东省第一届省赛

A: 可水可Trie,Trie解法

数据不大,因为题目没有给出字符串的大小,害怕暴力超时,所以用Trie写的.

#include<bits/stdc++.h>
using namespace std;
const int CHARSET=10,BASE='0',MAX_NODE=10100;
struct Trie{
    int tot,root,child[MAX_NODE][CHARSET];
    bool flag[MAX_NODE];
    bool has_prefix;
    bool is_root[MAX_NODE][CHARSET];
    Trie(){
        //printf("New Trie\n");
        memset(child[1],0,sizeof(child[1]));
        memset(is_root,false,sizeof(is_root));
        flag[1]=false;
        has_prefix=false;
        root=tot=1;
    }
    void insert(const char *str){
        int *cur=&root;
        char last_char;
        for(const char *p=str;*p;++p){
            cur=&child[*cur][*p-BASE];
            last_char=*p;
            if(is_root[*cur][last_char])has_prefix=true;
            if(*cur==0){
                *cur=++tot;
                memset(child[tot],0,sizeof(child[tot]));
                flag[tot]=false;
            }
        }
        flag[*cur]=true;
        is_root[*cur][last_char]=true;
    }

};
int main(){
    int n;
    while(~scanf("%d",&n) && n){
        Trie te;
        char str[10000];
        for(int i=0;i<n;++i){
            scanf("%s",str);
            if(!te.has_prefix){
                te.insert(str);
            }
        }
        if(te.has_prefix){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

B:思路比较清晰,就是写的时间长,我写了两份代码

单树(map)套结构体Point重载<+二分: 内存小,时间长

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Point{
    int x,y;
    bool operator < (const Point& a)const{
        if(x<a.x) return true;
        else if(x==a.x && y<a.y) return true;
        return false;
    }
    bool operator == (const Point& a)const{
        if(x==a.x && y==a.y) return true;
        return false;
    }

};
int N,kase=1;

int xx,yy;
char opt[10];

map<Point,bool> G;//x点集0,true为未删除,false为删除
map<Point,bool>::iterator it;

void init(){
    G.clear();
}

bool cmp(Point a,Point b){
    if(a.x<b.x && a.y<b.y)
        return true;
    return false;
}

void add(){
    G[(Point){xx,yy}]=true;
}

void find_(int a,int b){
    it=G.upper_bound((Point){a,b});
    if(it==G.end()){
        printf("-1\n");
        return;
    }
    Point nw=it->first;
    if(it->second && nw.x>xx && nw.y>yy){
        printf("%d %d\n",nw.x,nw.y);
    }else{
        do{
            it++;
            if(it==G.end()){printf("-1\n");return;}
            if(it->second && (it->first).x>xx && (it->first).y>yy){
                printf("%d %d\n",(it->first).x, (it->first).y);
                return;
            }
        }while(1);
    }
}

void remove_(){
    G[(Point){xx,yy}]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_(xx,yy);
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}

/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 904ms
Take Memory: 5752KB
Submit time: 2018-02-27 17:08:24
****************************************************/

树(map)+二分套树(map)+二分,代码少,时间短,内存大

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

int N,kase=1;

int xx,yy;
char opt[10];

map<int,map<int,bool> > G;//x点集0,true为未删除,false为删除
map<int,bool>::iterator ity;
map<int,map<int,bool> >::iterator itx;

void init(){
    G.clear();
}

void add(){
    (G[xx])[yy]=true;
}

void find_(){
    itx=G.upper_bound(xx);
    while(1){
        if(itx!=G.end()){
            ity=(itx->second).upper_bound(yy);
            if(ity!=(itx->second).end() && ity->second){
                printf("%d %d\n",itx->first,ity->first);
                return;
            }
            if(ity!=(itx->second).end()){
                for(ity++;ity!=(itx->second).end();ity++){
                    if(ity->second){
                        printf("%d %d\n",itx->first,ity->first);
                        return;
                    }
                }
            }
        }else break;
        itx++;
    }
    printf("-1\n");
}

void remove_(){
    (G[xx])[yy]=false;
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        printf("Case %d:\n",kase++);
        for(int i=0;i<N;++i){
            scanf("%s %d %d",opt,&xx,&yy);
            if(opt[0]=='a'){
                add();
            }else if(opt[0]=='f'){
                find_();
            }else{
                remove_();
            }
        }
        printf("\n");
    }
    return 0;
}


/***************************************************
User name: 奥术大师大所大
Result: Accepted
Take time: 516ms
Take Memory: 12712KB
Submit time: 2018-02-27 17:24:44
****************************************************/

然后我百度一下原题,发现set直接删除就好…还是STL不太熟,内存小,用时也少,不过没第二份少

    #include <iostream>  
    #include <stdio.h>  
    #include <algorithm>  
    #include <set>  
    #include <string>  
    using namespace std;  

    int main()  
    {  
        pair<int,int>p;  
        int n;char str[10];  
        int c=1;  
        while(cin>>n&&n)  
        {  
            cout<<"Case "<<c++<<":"<<endl;  
            set< pair<int,int> >s;  
            while(n--)  
            {  
                scanf("%s",str);  
                scanf("%d%d",&p.first,&p.second);  
                if(str[0]=='a')  
                    s.insert(p);  
                else if(str[0]=='r')  
                    s.erase(p);  
                else if(str[0]=='f')  
                {  
                    set< pair<int,int> >::iterator it;  
                    it=s.lower_bound(p);//找到set中第一个比p大的元素的位置,找不到则为s.end()  
                    for(;it!=s.end();it++)  
                    {  
                        if(it->first>p.first&&it->second>p.second)//都大于才符合题意  
                        {  
                            cout<<it->first<<" "<<it->second<<endl;  
                            break;  
                        }  
                    }  
                    if(it==s.end())//找不到  
                        cout<<-1<<endl;  
                }  
            }  
            cout<<endl;  
        }  
        return 0;  
    }  

貌似还可以用线段树优化..

F**k

C:排序水过,别问我为啥写的那么麻烦…因为我半截才想到,懒得改了

#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
struct Query{
    int s,t;
};
int N,kase=1;
int main(){
    while(~scanf("%d",&N) && N){
        priority_queue<int,vector<int>,greater<int> > G[maxn];
        priority_queue<int,vector<int>,greater<int> > it;
        vector<Query> Q;
        for(int i=1;i<=N;++i){
            int s,t;
            scanf("%d%d",&s,&t);
            G[s].push(t);
            Q.push_back((Query){s,t});
        }
        printf("Case %d:\n",kase++);
        for(int i=0;i<Q.size();++i){
            int s=Q[i].s,t=Q[i].t;
            bool has_ans=false;
            for(int j=s+1;j<=309 && !has_ans;++j){
                it=G[j];
                while(!it.empty()){
                    int nw=it.top();it.pop();
                    if(nw>t){
                        has_ans=true;
                        printf("%d %d\n",j,nw);
                        break;
                    }
                }
            }
            if(!has_ans){
                printf("-1 -1\n");
            }
        }
        printf("\n");
    }
    return 0;
}

D:中途相遇法+负值二分

因为内置的lower_bound只能查找第一个大于等于的,而我们需要的是小于等于的,所以将所有的值变成负数插入到vector中即可.

这道题N^4肯定是不可行的.所以我们考虑用中途相遇法,

即先处理出任意两个值的和,然后遍历和数组,在原数组中查找是否存在一个值和当前和相加<=M,如果等于M,break即可.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int maxn=2000;
int N,M,KASE=1;
int arr[maxn];
vector<int> first;
int main(){
    while(~scanf("%d%d",&N,&M) && N+M){
        first.clear();
        int ans=0;
        for(int i=0;i<N;++i) scanf("%d",&arr[i]);
        for(int i=0;i<N;++i){
            for(int j=i;j<N;++j){
                first.push_back(-(arr[i]+arr[j]));
            }
        }
        sort(first.begin(),first.end());
        for(int i=0;i<first.size();++i){
            int need=M+first[i];
            if(need<=0) continue;
            else{
                int id=lower_bound(first.begin(),first.end(),-need)-first.begin();
                int nw=-(first[i]+first[id]);
                if(nw<=M) ans=max(ans,nw);
            }
            if(ans==M)break;
        }
        printf("Case %d: %d\n\n",KASE++,ans);
    }
    return 0;
}

G:排序水过

一开始没读懂题意时最难受的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100100;
int Dist[maxn],N;
int main(){
    while(~scanf("%d",&N) && N){
        for(int i=0;i<N;++i){
            scanf("%d",&Dist[i]);
        }
        sort(Dist,Dist+N);
        LL ans=0ll;
        for(int i=1;i<N;++i){
            ans+=((Dist[i]-Dist[i-1])<<1);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

I:分别进行两个dfs即可,四方向和八方向

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

int move1[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int move2[8][2]={{0,-1},{0,1},{-1,0},{1,0},
                 {1,-1},{1,1},{-1,-1},{-1,1}};
char mp[110][110];
int N,kase=1;
int vis1[110][110],vis2[110][110];

void init(){
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
}

bool check(int x,int y){
    if(x>=N || y>=N || x<0 || y<0 || mp[x][y]=='0')
        return false;
    return true;
}

void dfs4(int x,int y){
    if(!check(x,y) || vis1[x][y]) return;
    vis1[x][y]=1;
    for(int i=0;i<4;++i){
        int nx=x+move1[i][0],ny=y+move1[i][1];
        dfs4(nx,ny);
    }
}

void dfs8(int x,int y){
    if(!check(x,y) || vis2[x][y]) return;
    vis2[x][y]=1;
    for(int i=0;i<8;++i){
        int nx=x+move2[i][0],ny=y+move2[i][1];
        dfs8(nx,ny);
    }
}

int main(){
    while(~scanf("%d",&N) && N){
        init();
        for(int i=0;i<N;++i){
            scanf("%s",mp[i]);
        }
        int ans4=0,ans8=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(mp[i][j]=='1' && !vis1[i][j]){
                    ans4++,dfs4(i,j);
                }
                if(mp[i][j]=='1' && !vis2[i][j]){
                    ans8++,dfs8(i,j);
                }
            }
        }
        printf("Case %d: %d %d\n\n",kase++,ans4,ans8);
    }
    return 0;
}

E:大模拟

大模拟

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
const int maxn=35;
int N,kase=1;
char mp[maxn][maxn];
int vis[maxn][maxn][maxn][maxn][5];
///EWSN东西南北
int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
///saya更喜欢EWNS
int nt[4][2]={{0,1},{0,-1},{-1,0},{1,0}};

bool check(int x,int y){
    if(x<0||y<0||x>=N||y>=N)return false;
    return true;
}
///返回当前的朝向在,数组为dis
int now_dir(int x,int y,int t){
    char str=mp[x][y];
    int in=0;
    if(str=='E') in=0;
    else if(str=='W') in=1;
    else if(str=='S') in=2;
    else in=3;
    in+=t;
    return in%4;
}

int dist(int x,int y,int tx,int ty){
    return (x-tx)*(x-tx)+(y-ty)*(y-ty);
}

int query_dir(int x,int y,int tx,int ty){
    int mind=INF,dir_=-1;
    for(int i=0;i<4;++i){
        int xx=x+nt[i][0],yy=y+nt[i][1];
        if(!check(xx,yy)) continue;
        int d=dist(xx,yy,tx,ty);
        if(mind>d){
            mind=d;
            dir_=i;
        }
    }
    ///返回第一个想走的方向
    return dir_;
}

int main(){
    while(scanf("%d",&N)!=EOF && N!=0){
        memset(vis,0,sizeof(vis));
        for(int i=0;i<N;++i){
            scanf("%s",&mp[i]);
        }
        int x=0,y=0,tx=N-1,ty=N-1,step=0;
        int xx,yy,txx,tyy;
        printf("Case %d:\n",kase++);
        while(1){
            if(step>=100){
                printf("Not sure.\n");
                break;
            }
            if(tx==x&&ty==y){
                printf("Get the treasure! At step %d.\n",step);
                break;
            }
            ///saya第一步
            int saya=now_dir(x,y,step);
            xx=x+dis[saya][0],yy=y+dis[saya][1];
            if(check(xx,yy)){
                x=xx,y=yy;
            }
            ///saya第二步
            if(!(x==tx&&y==ty)){
                int goal=query_dir(x,y,tx,ty);
                xx=x+nt[goal][0],yy=y+nt[goal][1];
                if(check(xx,yy)){
                    x=xx,y=yy;
                }
            }
            ///宝藏走
            int tres=now_dir(tx,ty,step);
            txx=tx+dis[tres][0],tyy=ty+dis[tres][1];
            if(check(txx,tyy)){
                tx=txx,ty=tyy;
            }

            if(vis[x][y][tx][ty][step%4]){
                printf("Impossible. At step %d.\n",step);
                break;
            }else{
                vis[x][y][tx][ty][step%4]=1;
            }
            step+=1;
        }
        printf("\n");
    }
    return 0;
}

HDU 1431

Link

http://acm.hdu.edu.cn/showproblem.php?pid=1431

type: 二分,线性素数筛

题意

题目很清楚,求a到b之间的回文素数,打印出来.

注意题目给的a,b范围为10000000,所以不能用朴素艾筛.

题解

先用线筛打1000W的表,然后二分查找a的下标,暴力a到b内素数是否是回文数即可.

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000000+10;
int a,b,tot=0;

bool valid[maxn];
int prime[maxn];
void init(int n,int ans[maxn]){
    memset(valid,true,sizeof(valid));
    for(int i=2;i<=n;++i){
        if(valid[i]){
            tot++;
            ans[tot]=i;
        }
        for(int j=1;((j<=tot) && (i*ans[j]<=n));++j){
            valid[i*ans[j]]=false;
            if(i%ans[j]==0) break;
        }
    }
}

int query(int len,int key){
    int left=1;
    int right=len;
    int mid;
    while(left<=right){
        mid=(left+right)>>1;
        if(key<prime[mid]){
            right=mid-1;
        }else if(key>prime[mid]){
            left=mid+1;
        }else return mid;
    }
    return -1;
}

bool check(int n){
    if((n/10)==0) return true;
    int str[20];
    int len=0,l=n;
    for(;l>0;){
        ++len;
        str[len]=l%10;
        l/=10;
    }
    for(int i=1;i<=len;++i){
        if(str[i]!=str[len-i+1]) return false;
    }
    return true;
}

int main(){
    init(10000000,prime);
    while(~scanf("%d %d",&a,&b)){
        int id=query(tot,a);
        for(int i=id;prime[i]<=b && prime[i];++i){
            if(check(prime[i])){
                printf("%d\n",prime[i]);
            }
        }
        printf("\n");
    }
    return 0;
}