「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) F

【思路】

因为时间是个天然的序,所以我们只需要去考虑蚂蚁的朝向和位置即可.而蚂蚁是否被吃也可以通过是否有和他相向而行的蚂蚁来判断.

用栈来边输入(输入是向右进行的,所以我们就让右行的蚂蚁固定,用左行的蚂蚁来吃与被吃..好残忍= =)边模拟这一过程.(其实只要是链表形式的都可以用来模拟,因为这样会节省时间

【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{
    int A,B;
};
stack<Star> Inti;
int N,A,B;
int main(){
    freopen(“in.txt”, “r”, stdin);
    freopen(“out.txt”, “w”, stdout);
    while(~scanf(“%d”,&N)){
        while(!Inti.empty()){
            Inti.pop();
        }
        rep(i,N){
            scanf(“%d%d”,&A,&B);
            //Inti.push_back((Star){A,B,true});
            if(B==1 || (!Inti.empty() && Inti.top().B==0)){
                Inti.push((Star){A,B});
            }else{
                int flag=0;
                while(!Inti.empty()){
                    if(Inti.top().B==1){
                        if(Inti.top().A<A){
                            Inti.pop();
                        }else{
                            flag=1;
                        }
                        if(flag) break;
                    }else break;
                }
                if(!flag){
                    Inti.push((Star){A,B});
                }
            }
        }
        printf(“%d\n”,Inti.size());
    }
    return 0;
}

【输入数据 in.txt】

12
8 1
5 0
3 1
6 0
7 1
4 0
1 1
9 0
2 1
13 0
15 1
32 0
5
4 0
3 1
2 0
1 0
5 0
12
8 0
5 1
3 0
6 1
7 0
4 1
1 0
9 1
2 0
13 1
15 0
32 1

【输出数据】

3
2
4

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【题目来源】

「游族杯」上海市高校程序设计邀请赛暨华东师范大学第九届 ECNU Coder 程序设计竞赛 (重现) A

【Tip】

找进位规律找的自己恶心吐了,最后跪在了百位进位时忘了加最后的那几次十进位…(最后也是对拍了一个ACcode才找到了错误的地方

思维漏洞还是太大了,或者说这种思维方式不太好.

不过也算是又学会了一点东西.

【My 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 main(){
    freopen(“in_2.txt”, “r”, stdin);
    freopen(“out_2.txt”, “w”, stdout);
    int T,N,M,B,C,EndN,EndM;
    while(~scanf(“%d”,&T)){
        int ca=1;
        while(T–){
            int REG1,REG2,D1,D2,ans=-INF,r1[3],r2[3],r11[3],r22[3];
            D1=D2=0;
            scanf(“%d%d”,&B,&C);
            REG1=B;
            REG2=C;
            red(i,2,0){
                r1[i]=REG1%10;REG1/=10;
                r2[i]=REG2%10;REG2/=10;
            }
            scanf(“%d”,&N);
            rep(i,N+1){//甲得i分,乙得M分
                int D11,D22,all;
                D11=D22=0;all=0;
                M=N-i;
                EndN=B+i;
                EndM=C+M;
                red(i,2,0){
                    r11[i]=EndN%10;EndN/=10;
                    r22[i]=EndM%10;EndM/=10;
                }//百位进位19 十位进位9
                r11[0]=r11[0]-r1[0];
                if(r11[0]) {
                    r11[1]=(r11[0]-1)*9+(9-r1[1])+r11[1];
                    all+=(r11[0]*18+r11[1]*9);
                }else{
                    r11[1]=r11[1]-r1[1];
                    all+=(r11[1]*9);
                }
                r22[0]=r22[0]-r2[0];
                if(r22[0]) {
                    r22[1]=(r22[0]-1)*9+(9-r2[1])+r22[1];
                    all+=(r22[0]*18+r22[1]*9);
                }else{
                    r22[1]=r22[1]-r2[1];
                    all+=(r22[1]*9);
                }
               // printf(“%d\n”,all+N);
                ans=max(ans,all+N);
            }
            printf(“Case %d: %d\n”,ca++,ans);
        }
    }
    return 0;
}

【效率&直观 code】

感觉处理方法类似于数位dp

    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 1005
    int dp[maxn];

    void init(){
        for(int i=1;i<=999;i++){
            if(i%100==0){
                dp[i]=dp[i-1]+19;
            }else if(i%10==0)
                dp[i]=dp[i-1]+10;
            else
                dp[i]=dp[i-1]+1;
        }
        return;
    }

    int main(){
        freopen(“in_2.txt”, “r”, stdin);
        freopen(“out_3.txt”, “w”, stdout);
        int T;
        cin>>T;
        init();
        for(int cas=1;cas<=T;cas++){
            int a,b,k;
            cin>>a>>b>>k;
            int ans=0;
            int tans=0;
            for(int i=0;i<=k;i++){
                tans=dp[a+i]-dp[a]+dp[b+k-i]-dp[b];
               // printf(“%d\n”,tans);
                ans=max(ans,tans);
            }
            cout<<“Case “<<cas<<“: “;
            cout<<ans<<“\n”;
        }
        return 0;
    }

【数据 in_2.txt】

13
000 000
1
000 000
10
000 000
100
001 000
109
001 001
109
123 123
89
458 253
500
327 652
200
320 602
58
227 725
63
102 103
37
023 001
900
21 23
5

【输出】

Case 1: 1
Case 2: 19
Case 3: 199
Case 4: 217
Case 5: 217
Case 6: 179
Case 7: 1013
Case 8: 398
Case 9: 112
Case 10: 126
Case 11: 73
Case 12: 1791
Case 13: 5