山东省第七届省赛

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

山东省第一届省赛

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

山东省第八届ACM省赛 fireworks

迟来的祝福,新年快乐.

Link

要登录

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3895.html

Type: 杨辉三角<-组合数学,逆元

题意

假设x位置有一个烟花,则每秒烟花都会分裂到x+1与x-1这两个位置.

给你n个烟花的初始位置xi和个数ci,问你T秒后,位置w上的烟花个数有多少个.

题解

画一下样例的图会发现很像杨辉三角,我们可以将每个初始点分开计算,最后的结果就是所有初始点分裂后落在目标点的烟花个数和.
但我们发现它们的初始值大小与杨辉三角不同,并且比杨辉三角多了许多0, 然后我们考虑如何解决这两个情况.

(1) 初始值ci,因为只有一个初始点,这点和杨辉三角一样.所以答案是

ans(原杨辉三角在该位置的结果)*ci

(2) 中间有0,这点好想,我们只需要通过推导公式将实际坐标转换为逻辑坐标即可.

然后我们分情况讨论,我们在图上可以发现

(1) 当 分裂次数目标位置和原位置的距离差 同奇偶时该位置结果为0.
(2) 当距离大于T+1时(即杨辉三角第T行值的个数),永远不可能分裂到.

因为只需要考虑最后一次分裂的结果,所以只需要计算杨辉三角第T行即可,即 C(T,0~T)
预处理组合公式我们用 组合数学 性质4那个公式.
所以我们需要预处理一下1~1e5的逆元,将除法转换为乘法.
最后答案就是

ans=Sigma(i=1~n,c*C[实际位置] | 根据情况忽略i)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int maxn = 1e5+7;

LL C[maxn];
///逆元
LL inv[maxn];
void init_(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(MOD-MOD/i)*1ll*inv[MOD%i]%MOD;
    }
}

///快速幂模求逆元,调动方式quick_mod(i,MOD-2)
//这里我们用预处理.
LL quick_mod(LL x, int n){
    LL ret = 1;
    while(n){
        if(n & 1) ret = ret * x % MOD;
        x = x * x %MOD;
        n >>= 1;
    }
    return ret;
}

void init(int t){
    C[0]=1;
    for(int i=1;i<=t;++i){
        C[i]=C[i-1]*(t-i+1)*1ll%MOD*inv[i]%MOD;
        //printf("Num: %d %lld, INV: %lld\n",i,C[i],inv[i]);
    }
}
//判断是否同奇同偶
bool same(int x,int y){
    if((x&1)^(y&1)) return false;
    return true;
}

int query(int t,int d){
    if(t&1){
        return t/2-d/2;
    }
    return t/2+(d-1)/2;
}

int main(){
    init_();
    int n,T,w;
    while(~scanf("%d%d%d",&n,&T,&w)){
        init(T);
        LL ans=0;
        for(int i=1;i<=n;++i){
            int x,c;
            scanf("%d%d",&x,&c);
            int dist=abs(x-w);
            if(!same(T+1,dist) && dist<T+1){
                ans=(ans+c*C[query(T+1,dist)]%MOD)%MOD;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}

第八届ACM省赛 K CF

CF

sdut 3903

Time Limit: 1000MS
Memory Limit: 65536KB

Problem Description

LYD loves codeforces since there are many Russian contests. In an contest lasting for T minutes there are n problems, and for the ith problem you can get aiditi points, where ai indicates the initial points, di indicates the points decreased per minute (count from the beginning of the contest), and ti stands for the passed minutes when you solved the problem (count from the begining of the contest).
Now you know LYD can solve the ith problem in ci minutes. He can’t perform as a multi-core processor, so he can think of only one problem at a moment. Can you help him get as many points as he can?

Input

The first line contains two integers n,T(0≤n≤2000,0≤T≤5000).
The second line contains n integers a1,a2,..,an(0<ai≤6000).
The third line contains n integers d1,d2,..,dn(0<di≤50).
The forth line contains n integers c1,c2,..,cn(0<ci≤400).

Output

Output an integer in a single line, indicating the maximum points LYD can get.

Example Input

3 10
100 200 250
5 6 7
2 4 10

Example Output

254

题意

有 n 道题目,每一道题都有一个初始分值 ai ,每个单位时间这道题的分数便会减少 di ,而我们可以在 ci 时间内做出这道题而得到分数,求在时间 T 内最多可以获得的分数。

题解

首先可以感觉出这是道0-1背包问题,然后我们需要知道,当我们做题时,会一两个角度来选择题目,其一是选择做题速度最快的,其二是选择做分值降低速度最快的.那么我们的衡量标准就可以看成先做单位时间内做题最多的那道.
然后我们根据上述规则排一下序.
在用排序后的数组进行0-1背包.在背包过程中记录最大值,即为最后的结果.

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

struct pro{
    int a,d,c;
    //按单位时间内减少分值排序
    bool operator <(const pro &pt)const{
        return 1.0*d/c>(1.0*pt.d/pt.c);
    }
};

int n,T;
pro p[maxn];
int dp[5010];
int main(){
    while(~scanf("%d%d",&n,&T)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].a);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].d);
        }
        for(int i=0;i<n;++i){
            scanf("%d",&p[i].c);
        }
        sort(p,p+n);
        int mx=-1;
        for(int i=0;i<n;++i){
            for(int j=T;j>=0;--j){
                if(j>=p[i].c){
                    dp[j]=max(dp[j],dp[j-p[i].c]+p[i].a-j*p[i].d);
                }
                mx=max(mx,dp[j]);
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}

第八届ACM省赛 Quadrat 找规律

原题连接: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/problemlist/cid/2164

B题

题意: 求数位为n位的所有数字(0~9..9(n个9))中,各个数位与其平方%10^n所得数的各个数位之差不超过d的数的个数.

注: 所有的数位之差是循环的,比如9和1差2.

首先打表(不过我认为这道题是数位dp,但我不会):

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int num[5]={1,10,100,1000,10000};
int a[15][15];
void init(){
    memset(a, 0, sizeof(a));
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j <= 9; ++j){
            a[i][j] = abs(i-j);
            if(a[i][j] > 5) a[i][j] = 10 - a[i][j];
        }
    }
}

bool judge(int i,int digit,int d){
    int res=i*i;
    for(int j=1;j<=digit;++j){
        int b=i%10;
        int c=res%10;
        i/=10;res/=10;
        if(a[b][c]>d) return false;
    }
    return true;
}

int check(int nb,int d){
    int cnt=0;
    for(int i=0;i<num[nb];++i){
        if(judge(i,nb,d))
            cnt++;
    }
    return cnt;
}

int main(){
    init();
    for(int i=1;i<=4;++i){
        printf("%d:",i);
        for(int j=0;j<4;++j){
            printf(" %d",check(i,j));
        }
        printf("\n");
    }
    return 0;
}

发现dp[i][j]=dp[i-1][j]*(2*j+1)

Code:

#include<cstdio>
#include<algorithm>
using namespace std;

long long dp[19][4];

void init(){
    dp[1][0]=4;dp[1][1]=4;
    dp[1][2]=8;dp[1][3]=8;
    for(int i=2;i<=18;++i){
        for(int j=0;j<4;++j){
            dp[i][j]=dp[i-1][j]*(2*j+1);
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d %d",&n,&d);
        printf("%lld\n",dp[n][d]);
    }
    return 0;
}

第六届山东省ACM/ICPC J Single Round Math

【类型】

java大整数瞎搞,话说占用内存好高啊.

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3260.html

【Code】

import java.util.*;
import java.math.*;
public class J{
    public static void main(String args[]){
        Scanner cin=new Scanner(System.in);
        int T;
        BigInteger a,b,c=new BigInteger(“11”),d=new BigInteger(“0”);
        T=cin.nextInt();
        while((T–)!=0){
            a=cin.nextBigInteger();
            b=cin.nextBigInteger();
            if(a.compareTo(c)<0 || b.compareTo(c)<0) System.out.println(“NO”);
            else if(a.compareTo(b)!=0) System.out.println(“NO”);
            else if(d.compareTo(a.remainder(c))==0) System.out.println(“YES”);
            else System.out.println(“NO”);
        }
    }
}

第六届山东省ACM/ICPC B Lowest Unique Price

【类型】

set,映射

【Tip】

题目上给的数据范围是 x∈[1,106]

但是我写代码时把映射空间开到100000才A了过去.?????? WTF??

另外,一开始我用map动态搜索,输出时遍历查找最少价值为一次的结果,果不其然,TLE.

所以改成了set动态更新第一个节点.即最小点.实现不需要遍历直接插入瞎搞的算法.

PS:真心搞不懂为啥映射数组要开10W啊???????

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

int reg[100000];
char readchar(){
char c=getchar();
while(c!=’b’ && c!=’q’ && c!=’c’) c=getchar();
return c;
}

int main(){
int T;
scanf(“%d”,&T);
while(T–){
set<int> se;
cle(reg,0);
int N;
SI(N);
rep(i,N){
char a;
int b;
a=readchar();
if(a==’b’){
SI(b);
reg[b]++;
if(reg[b]==1) se.insert(b);
else se.erase(b);
}
if(a==’c’){
SI(b);
if(reg[b]>0){
reg[b]–;
if(reg[b]==1) se.insert(b);
else se.erase(b);
}
}
if(a==’q’){
if(se.empty()) puts(“none”);
else printf(“%d\n”,*(se.begin()));
}
}

}
return 0;
}

第六届山东省ACM/ICPC A Nias and Tug-of-War

【类型】

重载小于号,排序

【题目链接】

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3251.html

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

struct star{
    double height,weight;
    bool operator<(const star A)const{
        return height<A.height;
    }
}person[200];

int main(){
    int T,N;
    double ansr=0.0,ansb=0.0;
    scanf(“%d”,&T);
    while(T–){
        ansr=0.0,ansb=0.0;
        scanf(“%d”,&N);
        rep(i,N)
            scanf(“%lf %lf”,&person[i].height,&person[i].weight);
        sort(person,person+N);
        int con=1;
        rep(i,N){
            if(con==1){
                con=0;
                ansr+=person[i].weight;
            }else{
                con=1;
                ansb+=person[i].weight;
            }
        }
        if(ansb>ansr)
            printf(“blue\n”);
        else if(ansr>ansb)
            printf(“red\n”);
        else   printf(“fair\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;
}