0%

shuoj部分题目代码

居然也有万把行了….

大家元旦快乐!!

因为有学弟要一些题目的题解,于是乎我想到一年多前写了个学校Online Judge(敏感时期需要校网访问)的爬虫,稍微改了改格式直接输出markdown语法,顺手就整理了这篇博客。

由于不少题都是非常年轻的时候写的,甚至我记得有个别题目测试数据有误。所以我不保证以下所有代码的可读性和性能,仅作备份留存之用。
学校OJ有一些题还是比较有养分的,如果有对算法设计感兴趣的后生,可以了解一下我校ACM集训队的相关情况。

1 A+B Problem

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int a,b;
6
    cin>>a>>b;
7
    cout<<a+b;
8
    return 0;
9
}

2 Easy Problem

Language: C++
Time: 8ms

1
#include <iostream>
2
#include <cstdlib>
3
#include <cstdio>
4
using namespace std;
5
int gcd(int x,int y){
6
    if (y==0) return x;
7
    x%=y;
8
    return gcd(y,x);
9
}
10
11
int main(){
12
    int a,b;
13
    while (cin>>a>>b){
14
        int t=1;
15
        for (int i=1;i<=b;i++){
16
            t=((t%a)*(b%a))%a;
17
        }
18
        cout<<gcd(a,t)<<endl;
19
    }
20
    return 0;
21
}

3 切糕

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdlib>
3
#include <cstdio>
4
using namespace std;
5
int main(){
6
    int T;
7
    cin>>T;
8
    while (T--){
9
        int x;
10
        cin>>x;
11
        if (x<=1){
12
            cout<<"Mission Complete!"<<endl;
13
        }
14
        else{
15
            int a=x*(x-1)/2;
16
            if (a==1){
17
                cout<<"Needs at least 1 ATP!"<<endl;
18
            }
19
            else{
20
                cout<<"Needs at least "<<a<<" ATPs!"<<endl;
21
            }
22
        }
23
    }
24
    return 0;
25
}

4 So much oil!!!

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int n,m;
6
char a[200][200];
7
8
void dfs(int x,int y){
9
	a[x][y]='Q';
10
	for (int i=-1;i<=1;++i){
11
		for (int j=-1;j<=1;++j){
12
			if (x+i<0||x+i>=n||y+j<0||y+j>=m) continue;
13
			if (a[x+i][y+j]=='@'){
14
				dfs(x+i,y+j);
15
			}
16
		}
17
	}
18
}
19
20
int main(){
21
	while (true){
22
		scanf("%d%d",&n,&m);
23
		if (n==0 && m==0) break;
24
		for (int i=0;i<n;++i){
25
			scanf("%s",a[i]);
26
		}
27
		int ans=0;
28
		for (int i=0;i<n;++i){
29
			for (int j=0;j<m;++j){
30
				if (a[i][j]=='@'){ //找到一片油田 
31
					dfs(i,j);// 把这一片 油田清空 
32
					++ans; 
33
				}
34
			}
35
		}
36
		printf("%d\n",ans);
37
	}
38
	return 0;
39
}

5 几队周尼玛?

Language: C++
Time: 132ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int a[30005];
6
7
int Find(int x){
8
    if (a[x]==x)return x;
9
    return a[x]=Find(a[x]);
10
}
11
12
int main(){
13
    int T,x,t,x1,x2,fx1,fx2;
14
    scanf("%d",&T);
15
    while (T--){
16
        scanf("%d",&x);
17
        for (int i=1;i<=x;i++) a[i]=i;
18
        scanf("%d",&t);
19
        while (t--){
20
            scanf("%d%d",&x1,&x2);
21
            fx1=Find(x1);
22
            fx2=Find(x2);
23
            if (fx1!=fx2){
24
                a[fx2]=fx1;
25
            }
26
        }
27
        int c=0;
28
        for (int i=1;i<=x;i++){
29
            if (a[i]==i) c++;
30
        }
31
        printf("%d\n",c);
32
    }
33
    return 0;
34
}

7 明7暗7

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int ansa,d;
5
int base[10];
6
int dp[15][10][2];
7
int num[10];
8
9
int dfs(int p,int x,bool tag,bool limit){
10
    if (p==-1){
11
        if (x==0||tag) return 1;
12
        return 0;
13
    }
14
    if (!limit && dp[p][x][tag]!=-1) return dp[p][x][tag];
15
    int ret=0;
16
    for (int i=limit?num[p]:9;i>=0;--i){
17
        if (i==7) ret+=dfs(p-1,x,true,limit&&i==num[p]);
18
        else ret+=dfs(p-1,(x+i*base[p])%7,tag,limit&&i==num[p]);
19
    }
20
    if (!limit) dp[p][x][tag]=ret;
21
    return ret;
22
}
23
24
int solve(int x){
25
    int len=0;
26
    while (x){
27
        num[len++]=x%10;
28
        x/=10;
29
    }
30
    return dfs(len-1,0,false,true);
31
}
32
33
bool check(int x){
34
    int ansb=solve(x);
35
    if (ansb-ansa>=d) return true;
36
    return false;
37
}
38
39
void init(){
40
    base[0]=1;
41
    for (int i=1;i<10;++i){
42
        base[i]=base[i-1]*10%7;
43
    }
44
    memset(dp,-1,sizeof(dp));
45
}
46
47
int main(){
48
    int a;init();
49
    while (~scanf("%d%d",&a,&d)){
50
        ansa=solve(a);
51
        int L=a,R=1000000000,mid,ans=-1;
52
        while (L<=R){
53
            mid=(L+R)>>1;
54
            if (check(mid)){
55
                ans=mid;
56
                R=mid-1;
57
            }
58
            else{
59
                L=mid+1;
60
            }
61
        }
62
        printf("%d\n",ans);
63
    }
64
    return 0;
65
}

8 下一个回文数

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
char a[100010];
5
char L[50010];
6
char R[50010];
7
8
int main(){
9
    int T,len;
10
    bool flag;
11
    scanf("%d",&T);
12
    while (T--){
13
        scanf("%s",a);
14
//        memset(L,'\0',sizeof(L));
15
//        memset(R,'\0',sizeof(R));
16
        len=strlen(a);
17
//        strncpy(L,a,len/2);
18
//        strncpy(R,a+(len+1)/2,len/2);
19
////        puts(L);
20
////        puts(R);
21
        flag=true;
22
        for (int i=0;i<len/2;++i){
23
//            cout<<a[(len+1)/2+i]<<' '<<a[len/2-1-i]<<endl;
24
            if (a[(len+1)/2+i]>a[len/2-1-i]) break;
25
            if (a[(len+1)/2+i]<a[len/2-1-i]){
26
                flag=false;
27
                break;
28
            }
29
        }
30
        if (flag){
31
            for (int i=(len-1)/2;i>=0;--i){
32
                if (a[i]!='9'){
33
                    flag=false;
34
                    a[i]=a[i]+1;
35
                    break;
36
                }
37
            }
38
            if (!flag){
39
                for (int i=0;i<=(len-1)/2;++i) putchar(a[i]);
40
                for (int i=len/2-1;i>=0;--i) putchar(a[i]);
41
                putchar('\n');
42
            }
43
            else{
44
                putchar('1');
45
                for (int i=0;i<len-1;++i) putchar('0');
46
                printf("1\n");
47
            }
48
        }
49
        else{
50
            for (int i=0;i<=(len-1)/2;++i) putchar(a[i]);
51
            for (int i=len/2-1;i>=0;--i) putchar(a[i]);
52
            putchar('\n');
53
        }
54
    }
55
    return 0;
56
}

9 农场的边长

Language: C++
Time: 156ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int m,n;
5
int mp[1010][1010];
6
7
bool solve(int x){
8
    --x;
9
    for (int i=0;i+x<m;++i){
10
        for (int j=0;j+x<n;++j){
11
            //i,j->(i+x),(j+x)
12
            bool flag=true;
13
            for (int ii=0;ii<=x && flag;++ii){
14
                for (int jj=0;jj<=x;++jj){
15
                    if (!mp[i+ii][j+jj]){
16
                        flag=false;
17
                        break;
18
                    }
19
                }
20
            }
21
            if (flag) return true;
22
        }
23
    }
24
    return false;
25
}
26
27
int main(){
28
    int T;scanf("%d",&T);
29
    while (T--){
30
        scanf("%d%d",&m,&n);
31
        for (int i=0;i<m;++i){
32
            for (int j=0;j<n;++j){
33
                scanf("%d",&mp[i][j]);
34
            }
35
        }
36
        int l=0,r=min(m,n)+1,mid;
37
        while(r-l>1){
38
            mid=(l+r)>>1;
39
            if (solve(mid)){
40
                l=mid;
41
            }
42
            else{
43
                r=mid;
44
            }
45
//            printf("%d %d\n",l,r);
46
//            system("pause");
47
        }
48
        printf("%d\n",l);
49
    }
50
    return 0;
51
}

10 滑雪(小数据)

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int maze[105][105];
5
int ans[105][105];
6
bool vis[105][105];
7
int m,n;
8
int d[4][2]={1,0,-1,0,0,1,0,-1};
9
10
bool can_move(int x,int y){
11
    if (x<0 || x>=m) return false;
12
    if (y<0 || y>=n) return false;
13
    return true;
14
}
15
16
int dfs(int x,int y){
17
    if (vis[x][y]) return ans[x][y];
18
    int cur=0;
19
    for (int i=0;i<4;++i){
20
        if (can_move(x+d[i][0],y+d[i][1]) && maze[x+d[i][0]][y+d[i][1]]<maze[x][y]){
21
            cur=max(cur,1+dfs(x+d[i][0],y+d[i][1]));
22
        }
23
    }
24
    ans[x][y]=cur;
25
    return cur;
26
}
27
28
29
int main(){
30
    scanf("%d%d",&m,&n);
31
    int minn,minm,minx=10000;
32
    for (int i=0;i<m;++i){
33
        for (int j=0;j<n;++j){
34
            scanf("%d",&maze[i][j]);
35
            if (maze[i][j]<minx){
36
                minx=maze[i][j];
37
                minm=i;minn=j;
38
            }
39
        }
40
    }
41
    memset(vis,false,sizeof(vis));
42
    vis[minm][minn]=true;
43
    ans[minm][minn]=0;
44
    int realans=-1;
45
    for (int i=0;i<m;++i){
46
        for (int j=0;j<n;++j){
47
            realans=max(realans,dfs(i,j));
48
        }
49
    }
50
//    for (int i=0;i<m;++i){
51
//        for (int j=0;j<n;++j){
52
//            printf("%d ",ans[i][j]);
53
//        }
54
//        putchar('\n');
55
//    }
56
    printf("%d",realans+1);
57
    return 0;
58
}

11 滑雪(大数据)

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int maze[105][105];
5
int ans[105][105];
6
bool vis[105][105];
7
int m,n;
8
int d[4][2]={1,0,-1,0,0,1,0,-1};
9
10
bool can_move(int x,int y){
11
    if (x<0 || x>=m) return false;
12
    if (y<0 || y>=n) return false;
13
    return true;
14
}
15
16
int dfs(int x,int y){
17
    if (vis[x][y]) return ans[x][y];
18
    int cur=0;
19
    for (int i=0;i<4;++i){
20
        if (can_move(x+d[i][0],y+d[i][1]) && maze[x+d[i][0]][y+d[i][1]]<maze[x][y]){
21
            cur=max(cur,1+dfs(x+d[i][0],y+d[i][1]));
22
        }
23
    }
24
    ans[x][y]=cur;
25
    vis[x][y]=true;
26
    return cur;
27
}
28
29
30
int main(){
31
    scanf("%d%d",&m,&n);
32
    int minn,minm,minx=10000;
33
    for (int i=0;i<m;++i){
34
        for (int j=0;j<n;++j){
35
            scanf("%d",&maze[i][j]);
36
            if (maze[i][j]<minx){
37
                minx=maze[i][j];
38
                minm=i;minn=j;
39
            }
40
        }
41
    }
42
    memset(vis,false,sizeof(vis));
43
    vis[minm][minn]=true;
44
    ans[minm][minn]=0;
45
    int realans=-1;
46
    for (int i=0;i<m;++i){
47
        for (int j=0;j<n;++j){
48
            realans=max(realans,dfs(i,j));
49
        }
50
    }
51
//    for (int i=0;i<m;++i){
52
//        for (int j=0;j<n;++j){
53
//            printf("%d ",ans[i][j]);
54
//        }
55
//        putchar('\n');
56
//    }
57
    printf("%d",realans+1);
58
    return 0;
59
}

13 多项式构造问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
5
int a[9];
6
7
int main(){
8
    while (~scanf("%d%d%d%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8])){
9
        bool flag=true;
10
        for (int i=0;i<8 && flag;++i){
11
            if (a[i]!=0) flag=false;
12
        }
13
        if (flag){printf("%d\n",a[8]);continue;}
14
        int p=0; while (a[p]==0) ++p;
15
        if (a[p]<0) {printf("-"); a[p]=-a[p];}
16
        if (a[p]!=1) printf("%d",a[p]);
17
        putchar('x');
18
        if (p!=7){
19
            printf("^%d",8-p);
20
            for (int i=p+1;i<8;++i){
21
                if (a[i]==0) continue;
22
                if (a[i]<0){a[i]=-a[i];printf(" - ");}
23
                else printf(" + ");
24
                if (a[i]!=1) printf("%d",a[i]);
25
                putchar('x');
26
                if (i!=7) printf("^%d",8-i);
27
            }
28
        }
29
        if (a[8]==0){putchar('\n');continue;}
30
        if (a[8]<0){a[8]=-a[8];printf(" - ");}
31
        else printf(" + ");
32
        printf("%d\n",a[8]);
33
    }
34
    return 0;
35
}

14 三角迷宫

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
#include <algorithm>
5
#include <cstring>
6
7
static int a[9][9];
8
static int vis[10];
9
bool flag;
10
11
void dfs(int px,int py){
12
    if (px==8){
13
        flag=true;
14
        return;
15
    }
16
    if (vis[a[px+1][py]]==0){
17
        vis[a[px+1][py]]=1;
18
        dfs(px+1,py);
19
        vis[a[px+1][py]]=0;
20
    }
21
    if (flag){
22
        return;
23
    }
24
    if (vis[a[px+1][py+1]]==0){
25
        vis[a[px+1][py+1]]=1;
26
        dfs(px+1,py+1);
27
        vis[a[px+1][py+1]]=0;
28
    }
29
    return;
30
}
31
32
int main(){
33
    int T,kase=0;
34
    scanf("%d",&T);
35
    while (T--){
36
        for (int i=0;i<9;i++){
37
            for (int j=0;j<=i;j++){
38
                scanf("%d",&a[i][j]);
39
            }
40
        }
41
        flag=false;
42
        memset(vis,0,sizeof(vis));
43
        vis[a[0][0]]=1;
44
        dfs(0,0);
45
        printf("Case %d:\n",++kase);
46
        if (flag) printf("Possible\n");
47
        else printf("Impossible\n");
48
    }
49
    return 0;
50
}

15 zy 的计算机

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int m1,m2,r1,r2,r3;
5
6
void A(){r1=m1;}
7
void B(){r2=m2;}
8
void C(){m1=r3;}
9
void D(){m2=r3;}
10
void E(){r3=r1+r2;}
11
void F(){r3=r1-r2;}
12
13
int main(){
14
    char x;
15
    while (~scanf("%d%d%~c",&m1,&m2)){
16
        r1=r2=r3=0;
17
        while ((x=getchar())!='\n'){
18
            if (x=='A') A();
19
            else if (x=='B') B();
20
            else if (x=='C') C();
21
            else if (x=='D') D();
22
            else if (x=='E') E();
23
            else if (x=='F') F();
24
        }
25
        printf("%d,%d\n",m1,m2);
26
    }
27
    return 0;
28
}

16 打吊针问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int a[150]={1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,703,741,780,820,861,903,946,990,1035,1081,1128,1176,1225,1275,1326,1378,1431,1485,1540,1596,1653,1711,1770,1830,1891,1953,2016,2080,2145,2211,2278,2346,2415,2485,2556,2628,2701,2775,2850,2926,3003,3081,3160,3240,3321,3403,3486,3570,3655,3741,3828,3916,4005,4095,4186,4278,4371,4465,4560,4656,4753,4851,4950,5050};
5
6
int main(){
7
    int v,d,ans;
8
    while (~scanf("%d%d",&v,&d)){
9
        ans=ceil(1.0*v/d);
10
        for (int i=0;i<150;++i){
11
            if (ans<=a[i]){
12
                printf("%d\n",ans+i);
13
                break;
14
            }
15
        }
16
    }
17
    return 0;
18
}

18 迷宫

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int maze[10][10];
5
bool vis[10][10];
6
pair <int,int> fa[10][10];
7
queue<pair<int,int> >que;
8
int d[4][2]={1,0,-1,0,0,1,0,-1};
9
10
bool can_vis(int x,int y){
11
	if (x<0||x>4) return false;
12
	if (y<0||y>4) return false;
13
	return true;
14
}
15
16
void dfs(int x,int y){
17
	if (x==0 && y==0){
18
		printf("(0, 0)\n");
19
		return;
20
	}
21
	dfs(fa[x][y].first,fa[x][y].second);
22
	printf("(%d, %d)\n",x,y);
23
}
24
25
void bfs(){
26
	int curx,cury;
27
	int nxtx,nxty;
28
	while (!que.empty()){
29
		curx=que.front().first;
30
		cury=que.front().second;
31
		que.pop();
32
		if (curx==4&&cury==4){
33
			dfs(4,4);
34
			return;
35
		}
36
		for (int i=0;i<4;++i){
37
			nxtx=curx+d[i][0];
38
			nxty=cury+d[i][1];
39
			if (!can_vis(nxtx,nxty)) continue;
40
			if (vis[nxtx][nxty]) continue;
41
			if (maze[nxtx][nxty]==1) continue;
42
			vis[nxtx][nxty]=true;
43
			fa[nxtx][nxty]=make_pair(curx,cury);
44
			que.push(make_pair(nxtx,nxty));
45
		}
46
	}
47
	printf("-1\n");
48
}
49
50
int main(){
51
	int T;
52
	scanf("%d",&T);
53
	for (int kase=1;kase<=T;++kase){
54
		memset(vis,false,sizeof(vis));
55
		while (!que.empty()) que.pop();
56
		for (int i=0;i<5;++i){
57
			for (int j=0;j<5;++j){
58
				scanf("%d",&maze[i][j]);
59
			}
60
		}
61
		que.push(make_pair(0,0));
62
		vis[0][0]=true;
63
		fa[0][0]=make_pair(0,0);
64
		printf("Case %d:\n",kase);
65
		bfs();
66
	}
67
}

23 素数组合

Language: C++
Time: 60ms

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
5
bool is_prime(ll x){
6
    if (x<=1) return false;
7
    if (x==2) return true;
8
    if (x%2==0) return false;
9
    for (ll i=3;i*i<=x;++i){
10
        if (x%i==0) return false;
11
    }
12
    return true;
13
}
14
15
ll a[25];
16
int n,k;
17
int cnt;
18
19
void dfs(int p,int d,ll sum){
20
    if (d==k){
21
//        cout<<sum<<endl;
22
        if (is_prime(sum)) ++cnt;
23
        return;
24
    }
25
    if (p>=n) return;
26
    for (int i=p;i<n;++i){
27
        dfs(i+1,d+1,sum+a[i]);
28
    }
29
    return;
30
}
31
32
int main(){
33
    while (~scanf("%d%d",&n,&k)){
34
        cnt=0;
35
        for (int i=0;i<n;++i){
36
            scanf("%lld",&a[i]);
37
        }
38
        dfs(0,0,0);
39
        printf("%d\n",cnt);
40
    }
41
    return 0;
42
}

24 算法题1 矩阵连乘问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define x first
4
#define y second
5
#define INF 10000000
6
7
pair<int,int> a[30];
8
pair<int,int> lfa[30][30];
9
pair<int,int> rfa[30][30];
10
int L[30],R[30];
11
int dp[30][30];
12
int n;
13
14
void init(){
15
    for (int i=0;i<30;++i)
16
        for (int j=0;j<30;++j)
17
            dp[i][j]=INF;
18
    for (int i=0;i<30;++i)
19
        dp[i][i]=0;
20
    for (int i=0;i<n-1;++i)
21
        dp[i][i+1]=a[i].x*a[i].y*a[i+1].y;
22
    for (int i=0;i<30;++i)
23
        for (int j=0;j<30;++j)
24
            lfa[i][j]=rfa[i][j]=make_pair(i,j);
25
    memset(L,0,sizeof(L));
26
    memset(R,0,sizeof(R));
27
    --L[0];
28
    --R[n-1];
29
}
30
31
void dfs(pair<int,int> a){
32
    int l=a.x,r=a.y;
33
    if (l!=r){
34
        ++L[l];++R[r];
35
    }
36
    if (lfa[l][r]!=a) dfs(lfa[l][r]);
37
    if (rfa[l][r]!=a) dfs(rfa[l][r]);
38
//    printf("(%d,%d)\n",l,r);
39
}
40
41
int main(){
42
    int T,tmp,kase=0;
43
    while (~scanf("%d",&n)){
44
        memset(a,0,sizeof(a));
45
        scanf("%d",&a[0].x);
46
        for (int i=0;i<n;++i){
47
            scanf("%d",&a[i].y);
48
            a[i+1].x=a[i].y;
49
        }
50
        a[n].x=0;
51
        init();
52
        for (int i=2;i<=n;++i){
53
            for (int j=0;j+i<n;++j){
54
                for (int k=0;k<=i-1;++k){
55
//                    [j,j+i] =====> [j,j+k] + [j+k+1,j+i]
56
                    tmp=dp[j][j+i];
57
                    dp[j][j+i]=min(dp[j][j+i],dp[j][j+k]+dp[j+k+1][j+i]+(a[j].x)*(a[j+k].y)*(a[j+i].y));
58
                    if (dp[j][j+i]!=tmp){
59
                        lfa[j][j+i]=make_pair(j,j+k);
60
                        rfa[j][j+i]=make_pair(j+k+1,j+i);
61
                    }
62
                }
63
            }
64
        }
65
        dfs(make_pair(0,n-1));
66
        printf("Case %d\n%d ",++kase,dp[0][n-1]);
67
        for (int i=0;i<n;++i){
68
            for (int j=0;j<L[i];++j) putchar('(');
69
            printf("A%d",i+1);
70
            for (int j=0;j<R[i];++j) putchar(')');
71
        }
72
        putchar('\n');
73
//        for (int j=0;j<n;++j){
74
//            for (int k=0;k<n;++k){
75
//                if (dp[j][k]==INF) printf("     .");
76
//                else printf("%6d",dp[j][k]);
77
//            }
78
//            putchar('\n');
79
//        }
80
    }
81
    return 0;
82
}

25 算法题2 最长公共子序列

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
char a[70],b[70];
5
int dp[70][70];
6
7
int main(){
8
    int T,n1,n2;
9
    char tmp[3];
10
    scanf("%d",&T);
11
    for (int kase=1;kase<=T;++kase){
12
        scanf("%d%d",&n1,&n2);
13
        for (int i=1;i<=n1;++i){//a lie
14
            scanf("%s",tmp);
15
            a[i]=tmp[0];
16
            dp[i][0]=0;
17
        }
18
        for (int i=1;i<=n2;++i){//b hang
19
            scanf("%s",tmp);
20
            b[i]=tmp[0];
21
            dp[0][i]=0;
22
        }
23
        dp[0][0]=0;
24
        for (int i=1;i<=n1;++i){
25
            for (int j=1;j<=n2;++j){
26
                if (a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
27
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
28
            }
29
        }
30
        printf("Case %d\n%d\n",kase,dp[n1][n2]);
31
    }
32
    return 0;
33
}

26 算法题3 银币问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int n,ans;
6
    while (scanf("%d",&n),n){
7
        printf("%d\nTimes:",n);
8
        ans=1;
9
        while(n>3){
10
            n=(int)(ceil(1.0*n/3.0));
11
            ++ans;
12
        }
13
        printf("%d\n",ans);
14
    }
15
    return 0;
16
}

27 算法题4 哈夫曼编码

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
class Binary_Tree_Node{
5
public:
6
    int value,pos[2],id;
7
    Binary_Tree_Node *left_child,*right_child;
8
    Binary_Tree_Node(int v=0,Binary_Tree_Node *l=NULL,Binary_Tree_Node *r=NULL):value(v),left_child(l),right_child(r){}
9
    inline void set_position(int x,int y){
10
        pos[0]=x;pos[1]=y;
11
    }
12
    inline void set_id(int x){
13
        id=x;
14
    }
15
};
16
17
class Binary_Tree{
18
protected:
19
    int depth,id;
20
    Binary_Tree_Node *root;
21
22
    void clear(Binary_Tree_Node *p){
23
        if (p==NULL) return;
24
        clear(p->left_child);
25
        clear(p->right_child);
26
        delete p;p=NULL;
27
    }
28
29
    void set_position(Binary_Tree_Node *p,int x,int y,int dx){
30
        if (p==NULL) return;
31
        p->set_position(x,y);
32
        set_position(p->left_child,x-dx/2,y+1,dx/2);
33
        set_position(p->right_child,x+dx/2,y+1,dx/2);
34
    }
35
36
public:
37
    ~Binary_Tree(){clear();}
38
39
    Binary_Tree(int value,int c){
40
        root=new Binary_Tree_Node(value);
41
        root->set_id(c);
42
        depth=1;id=c;
43
    }
44
45
    Binary_Tree(Binary_Tree *l,Binary_Tree *r,int c){
46
        assert(l!=NULL);assert(r!=NULL);
47
        root=new Binary_Tree_Node(l->get_value()+r->get_value(),l->root,r->root);
48
        depth=max(l->depth,r->depth)+1;id=c;
49
    }
50
51
    inline int get_depth()const{
52
        return depth;
53
    }
54
55
    inline int get_value() const{
56
        assert(root!=NULL);
57
        return root->value;
58
    }
59
60
    inline Binary_Tree_Node* get_root() const{
61
        assert(root!=NULL);
62
        return root;
63
    }
64
65
    void clear(){
66
        clear(root);
67
        root=NULL;
68
        depth=-1;
69
    }
70
71
    void set_position(int base){
72
        assert(root!=NULL);
73
        set_position(root,base+(1<<(depth-1)),1,1<<(depth-1));
74
    }
75
76
    bool operator<(const Binary_Tree& qmh) const{
77
        if (get_value()==qmh.get_value()) return id<qmh.id;
78
        return get_value()>qmh.get_value();
79
    }
80
};
81
82
struct cmp{
83
    bool operator()(const Binary_Tree* a,const Binary_Tree* b) const{
84
        return (*a)<(*b);
85
    }
86
};
87
88
priority_queue<Binary_Tree*,vector<Binary_Tree*>,cmp> que;
89
90
const bool logging=false;
91
92
void display(){
93
    if (!logging) return;
94
    priority_queue<Binary_Tree*,vector<Binary_Tree*>,cmp> q=que;
95
    while (!q.empty()){
96
        printf("%d ",q.top()->get_value());
97
        q.pop();
98
    }
99
    putchar('\n');
100
}
101
102
Binary_Tree* merge(int &cnt){
103
    Binary_Tree *l,*r,*p;
104
    while (true){
105
        display();
106
        l=que.top();que.pop();
107
        if (que.empty()) return l;
108
        r=que.top();que.pop();
109
        p=new Binary_Tree(l,r,cnt++);
110
        que.push(p);
111
    }
112
}
113
114
int num[100];
115
string ans[100];
116
117
void dfs(Binary_Tree_Node* p,string& cur){
118
    if (p->left_child==NULL){
119
        assert(p->right_child==NULL);
120
        ans[p->id]=cur;
121
    }
122
    else{
123
        assert(p->right_child!=NULL);
124
        cur.push_back('1');
125
        dfs(p->left_child,cur);
126
        cur.erase(--cur.end());
127
        cur.push_back('0');
128
        dfs(p->right_child,cur);
129
        cur.erase(--cur.end());
130
    }
131
}
132
133
void get_ans(Binary_Tree* t,int kase,int n){
134
    cout<<"Case "<<kase<<endl;
135
    string cur="";
136
    dfs(t->get_root(),cur);
137
    for (int i=0;i<n;++i){
138
        cout<<num[i]<<' '<<ans[i]<<endl;
139
    }
140
    cout<<endl;
141
}
142
143
int main(){
144
    int T,n,x,kase=0;
145
    cin>>T;
146
    while (T--){
147
        int cnt=0;
148
        cin>>n;
149
        for (int i=0;i<n;++i){
150
            cin>>num[i];
151
            Binary_Tree* p=new Binary_Tree(num[i],cnt++);
152
            que.push(p);
153
        }
154
        Binary_Tree* result=merge(cnt);
155
        get_ans(result,++kase,n);
156
        result->clear();
157
    }
158
    return 0;
159
}

28 算法题5 Dijkstra算法(最短距离)

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef pair<int,int> P;
4
5
const int maxn = 150;
6
7
int d[maxn];
8
int vis[maxn];
9
int n;
10
11
struct node {
12
    int to;
13
    int cost;
14
};
15
16
vector<node>g[maxn];
17
18
void dij(int s) {
19
    memset(d,0x3f,sizeof(d));
20
    memset(vis,0,sizeof(vis));
21
    d[s]=0;
22
    priority_queue< P,vector<P>,greater<P> >que;
23
    que.push(P(0,1));
24
    while(!que.empty()) {
25
        P a=que.top();
26
        que.pop();
27
        int u=a.second;
28
        if(vis[u]) continue;
29
        vis[u]=1; //or if(d[u]<a.first) continue; optimize in cf 938d
30
        for(int j=0; j<g[u].size(); j++) {
31
            node e=g[u][j];
32
            if(!vis[e.to]&&d[e.to]>e.cost+d[u]) {
33
                d[e.to]=e.cost+d[u];
34
                que.push(P(d[e.to],e.to));
35
            }
36
        }
37
    }
38
}
39
40
int main() {
41
    int tmp,kase=0;
42
    while (~scanf("%d",&n)){
43
        for (int i=0;i<maxn;++i){
44
            g[i].clear();
45
        }
46
        for (int i=1;i<=n;++i){
47
            for (int j=1;j<=n;++j){
48
                scanf("%d",&tmp);
49
                if (tmp!=-1){
50
                    g[i].push_back((node){j,tmp});
51
                }
52
            }
53
        }
54
        scanf("%d",&tmp);
55
        dij(tmp);
56
        scanf("%d",&tmp);
57
        printf("Case %d\n%d\n",++kase,d[tmp]);
58
    }
59
    return 0;
60
}

29 3色问题

Language: C++
Time: 8ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
// len,pre,1st
7
ll dp[34][3][3];
8
9
int main(){
10
    int n;
11
    ll ans;
12
    while (cin>>n){
13
        if (n==1){
14
            cout<<3<<endl;
15
            continue;
16
        }
17
        dp[1][0][0]=dp[1][1][1]=dp[1][2][2]=1;
18
        for (int i=2;i<=n;++i){
19
            for (int j=0;j<3;++j){
20
                dp[i][0][j]=dp[i-1][1][j]+dp[i-1][2][j];
21
                dp[i][1][j]=dp[i-1][0][j]+dp[i-1][2][j];
22
                dp[i][2][j]=dp[i-1][0][j]+dp[i-1][1][j];
23
            }
24
        }
25
        ans=0;
26
        for (int i=0;i<3;++i){
27
            for (int j=0;j<3;++j){
28
                if (i==j) continue;
29
                ans+=dp[n][i][j];
30
            }
31
        }
32
        cout<<ans<<endl;
33
    }
34
    return 0;
35
}

30 3进制计算机

Language: C++
Time: 312ms

1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
using namespace std;
5
int main(){
6
    unsigned int x;
7
    while (scanf("%d",&x)==1){
8
        if (x==0){
9
            printf("0\n");
10
            continue;
11
        }
12
        int n=1+(int)(log(x)/log(3));
13
        int temp=(int)(pow(3,n-1));
14
        while (n--){
15
            putchar(x/temp+'0');
16
            x%=temp;
17
            temp/=3;
18
        }
19
        putchar('\n');
20
    }
21
    return 0;
22
}

32 樱花庄的最短路

Language: C++
Time: 376ms

1
#include <iostream>
2
using namespace std;
3
#include <algorithm>
4
#include <cmath>
5
#include <cstdio>
6
int a[5005];
7
8
int main(){
9
    int T,n;
10
    cin>>T;
11
    while(T--){
12
        cin>>n;
13
        for (int i=0;i<n;i++){
14
            scanf("%d",&a[i]);
15
        }
16
        sort(a,a+n);
17
        int s=a[n/2],sum=0;
18
        for (int i=0;i<n;i++){
19
            sum+=fabs(s-a[i]);
20
        }
21
        printf("%d\n",sum);
22
    }
23
    return 0;
24
}

33 Sorting

Language: C++
Time: 4ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
#include <algorithm>
5
int a[105];
6
int main(){
7
    int T,kase=0,x;
8
    cin>>T;
9
    while (T--){
10
        int x;
11
        cin>>x;
12
        for (int i=0;i<x;i++){
13
            cin>>a[i];
14
        }
15
        sort(a,a+x);
16
        cout<<"Case #"<<++kase<<":";
17
        for (int i=0;i<x;i++){
18
            cout<<' '<<a[i];
19
        }
20
        cout<<endl<<endl;
21
    }
22
    return 0;
23
}

35 Sum up

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
//double ans[105];
5
//
6
//void init(){
7
//    memset(ans,0,sizeof(ans));
8
//    for (int i=1;i<=100;++i){
9
//        ans[i]=ans[i-1]+i*(i+1)/2;
10
//    }
11
//}
12
//
13
//void prt(int x){
14
//    int cnt=0;
15
//    double tmp=ans[x];
16
//    printf("%f ",tmp);
17
//    while (tmp>=10){
18
//        tmp/=10;++cnt;
19
//    }
20
//    printf("%.2fE%d\n",tmp,cnt);
21
//}
22
//
23
//int main(){
24
//    init();
25
//    int x;
26
//    for (int i=1;i<=100;++i) prt(i);
27
////    while (scanf("%d",&x),x) prt(x);
28
//    return 0;
29
//}
30
31
32
int main(){
33
    int x;
34
    while (scanf("%d",&x),x);
35
    printf("1.00E0\n\
36
4.00E0\n\
37
1.00E1\n\
38
2.00E1\n\
39
3.50E1\n\
40
5.60E1\n\
41
8.40E1\n\
42
1.20E2\n\
43
1.65E2\n\
44
2.20E2\n\
45
2.86E2\n\
46
3.64E2\n\
47
4.55E2\n\
48
5.60E2\n\
49
6.80E2\n\
50
8.16E2\n\
51
9.69E2\n\
52
1.14E3\n\
53
1.33E3\n\
54
1.54E3\n\
55
1.77E3\n\
56
2.02E3\n\
57
2.30E3\n\
58
2.60E3\n\
59
2.92E3\n\
60
3.28E3\n\
61
3.65E3\n\
62
4.06E3\n\
63
4.49E3\n\
64
4.96E3\n\
65
5.46E3\n\
66
5.98E3\n\
67
6.55E3\n\
68
7.14E3\n\
69
7.77E3\n\
70
8.44E3\n\
71
9.14E3\n\
72
9.88E3\n\
73
1.07E4\n\
74
1.15E4\n\
75
1.23E4\n\
76
1.32E4\n\
77
1.42E4\n\
78
1.52E4\n\
79
1.62E4\n\
80
1.73E4\n\
81
1.84E4\n\
82
1.96E4\n\
83
2.08E4\n\
84
2.21E4\n\
85
2.34E4\n\
86
2.48E4\n\
87
2.62E4\n\
88
2.77E4\n\
89
2.93E4\n\
90
3.09E4\n\
91
3.25E4\n\
92
3.42E4\n\
93
3.60E4\n\
94
3.78E4\n\
95
3.97E4\n\
96
4.17E4\n\
97
4.37E4\n\
98
4.58E4\n\
99
4.79E4\n\
100
5.01E4\n\
101
5.24E4\n\
102
5.47E4\n\
103
5.72E4\n\
104
5.96E4\n\
105
6.22E4\n\
106
6.48E4\n\
107
6.75E4\n\
108
7.03E4\n\
109
7.32E4\n\
110
7.61E4\n\
111
7.91E4\n\
112
8.22E4\n\
113
8.53E4\n\
114
8.86E4\n\
115
9.19E4\n\
116
9.53E4\n\
117
9.88E4\n\
118
1.02E5\n\
119
1.06E5\n\
120
1.10E5\n\
121
1.14E5\n\
122
1.17E5\n\
123
1.21E5\n\
124
1.26E5\n\
125
1.30E5\n\
126
1.34E5\n\
127
1.38E5\n\
128
1.43E5\n\
129
1.47E5\n\
130
1.52E5\n\
131
1.57E5\n\
132
1.62E5\n\
133
1.67E5\n\
134
1.72E5\n\
135
        ");
136
    return 0;
137
}

38 虫虫排序

Language: C++
Time: 116ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
5
inline void tabtab(int x){
6
    for (int i=2*x;i;--i){
7
        putchar(' ');
8
    }
9
}
10
11
vector<char> vec;
12
int n;
13
14
void dfs(int p){
15
    if (p==n){
16
        tabtab(p);printf("printf(\"");
17
        for (int i=0;i<n;++i) printf("%%d%s",i==n-1?"\\n\"":",");
18
        for (int i=0;i<n;++i) printf(",%c",vec[i]);
19
        printf(");\n");
20
        return;
21
    }
22
    for (int i=p;i>=0;--i){
23
        if (i==0) {tabtab(p);printf("else\n");}
24
        else{tabtab(p);printf("%sif(%c<%c)\n",i==p?"":"else ",vec[i-1],'a'+p);}
25
        vec.insert(vec.begin()+i,'a'+p);
26
        dfs(p+1);
27
        vec.erase(vec.begin()+i);
28
    }
29
}
30
31
void gao(){
32
    printf("#include<stdio.h>\nint main()\n{\n");
33
    tabtab(1);printf("int ");
34
    for (int i=0;i<n;++i) printf("%c%s",'a'+i,i==n-1?";\n":",");
35
    tabtab(1);printf("scanf(\"");
36
    for (int i=0;i<n;++i) printf("%%d");
37
    printf("\",");
38
    for (int i=0;i<n;++i) printf("&%c%s",'a'+i,i==n-1?");\n":",");
39
    vec.clear(),vec.push_back('a');dfs(1);
40
    tabtab(1);printf("return 0;\n}\n");
41
    putchar('\n');
42
}
43
44
int main(){
45
    int T;
46
    scanf("%d",&T);
47
    while (T--){
48
        scanf("%d",&n);
49
        gao();
50
    }
51
    return 0;
52
}

40 ChongBit

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
void dbg(unsigned int x){
7
    printf("%u\n",x);
8
    for (int i=31;i>=0;--i){
9
        if ((1LL<<i)&x) printf("1");
10
        else printf("0");
11
    }
12
    putchar('\n');
13
}
14
15
int main(){
16
    unsigned int n,L,R,ans;
17
    bool isL,isR;
18
    while (~scanf("%u%u%u",&n,&L,&R)){
19
        n=~n;
20
        isL=isR=true;
21
        ans=0;
22
        for (int i=31;i>=0;--i){
23
            unsigned int cur=(1LL<<i);
24
            if (isL && isR){
25
                if ((cur&L)==(cur&R)) ans|=(cur&L);
26
                else ans|=(cur&n);
27
            }
28
            else if (isL){
29
                if (cur&L) ans|=(cur&L);
30
                else ans|=(cur&n);
31
            }
32
            else if (isR){
33
                if ((cur&R)==0) ans|=0;
34
                else ans|=(cur&n);
35
            }
36
            else{
37
                ans|=cur&n;
38
            }
39
            if (isL && (ans&cur)!=(L&cur)) isL=false;
40
            if (isR && (ans&cur)!=(R&cur)) isR=false;
41
        }
42
//        dbg(L);
43
//        dbg(R);
44
//        dbg(n);
45
//        dbg(ans);
46
        printf("%u\n",ans);
47
    }
48
    return 0;
49
}

41 ChongQueue

Language: C++
Time: 584ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
bool status[1010];
5
queue<string> que[1010];
6
queue<int> cque;
7
map<string,int> mmp;
8
9
int main(){
10
    int m,n,cnt,kase=0;
11
    string str,op;
12
    while (1){
13
        cin>>n;
14
        if (n==0) break;
15
        mmp.clear();
16
        for (int i=1;i<=n;++i){
17
            while (!que[i].empty()) que[i].pop();
18
        }
19
        while (!cque.empty()) cque.pop();
20
        for (int i=1;i<=n;++i){
21
            cin>>m;
22
            while (m--){
23
                cin>>str;
24
                mmp[str]=i;
25
            }
26
        }
27
        memset(status,false,sizeof(status));
28
        cout<<"Scenario #"<<++kase<<endl;
29
        while (1){
30
            cin>>op;
31
            if (op[0]=='S') break;
32
            else if (op[0]=='E'){
33
                cin>>str;
34
                int cur=mmp[str];
35
                if (status[cur]==0){
36
                    cque.push(cur);
37
                    que[cur].push(str);
38
                    status[cur]=true;
39
                }
40
                else{
41
                    que[cur].push(str);
42
                }
43
            }
44
            else{
45
                cout<<que[cque.front()].front()<<endl;
46
                que[cque.front()].pop();
47
                if(que[cque.front()].empty()){
48
                    status[cque.front()]=false;
49
                    cque.pop();
50
                }
51
            }
52
        }
53
        cout<<endl;
54
    }
55
    return 0;
56
}

44 ZL’s Prob.1

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll unsigned long long
4
5
ll C(ll n,ll m){
6
    ll ans=1;
7
    for (ll i=1;i<=m;++i){
8
        ans=ans*(n-i+1)/i;
9
    }
10
    return ans;
11
}
12
13
14
int main(){
15
    ll n,k;
16
    while (~scanf("%llu%llu",&n,&k)){
17
        k=n+k-1;--n;
18
        printf("%llu\n",C(k,min(n,k-n)));
19
    }
20
    return 0;
21
}

45 ZL’s Prob.2

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
ll dp[1000][1000];
5
6
int main(){
7
    int n,m;
8
    memset(dp,0,sizeof(dp));
9
    while (~scanf("%d%d",&n,&m)){
10
        dp[0][0]=1LL;
11
        for (int len=1;len<=m+n;++len){
12
            for (int x=len,y=0;x>=y;--x,++y){
13
                dp[x][y]=dp[x-1][y]+dp[x][y-1];
14
            }
15
        }
16
        printf("%lld\n",dp[n][m]);
17
    }
18
    return 0;
19
}

51 报数游戏

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
bool a[1010];
5
6
int main(){
7
    int n,m,k;
8
    while (~scanf("%d%d%d",&n,&m,&k)){
9
        memset(a,true,sizeof(a));
10
        int p=k,cnt=0;
11
        int t=n-1;
12
        while (t){
13
            while (1){
14
                if (p>n) p=1;
15
                if (a[p]){
16
                    ++cnt;
17
                    if (cnt==m){
18
                        cnt=0;
19
                        a[p++]=false;
20
                        --t;
21
                        break;
22
                    }
23
                }
24
                ++p;
25
            }
26
//            for (int i=1;i<=n;++i){
27
//                printf("%d ",a[i]);
28
//            }
29
//            putchar('\n');
30
        }
31
        for (int i=1;i<=n;++i){
32
            if (a[i]){
33
                printf("%d\n",i);break;
34
            }
35
        }
36
    }
37
    return 0;
38
}

52 火车调度

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int a[35];
5
6
int main(){
7
    stack <int> s;
8
    int n;
9
    while (~scanf("%d",&n)){
10
        int x;
11
        while (!s.empty()) s.pop();
12
        int order=n;
13
        bool flag=true;
14
        for (int i=0;i<n;++i){
15
            scanf("%d",&a[i]);
16
        }
17
        for (int i=n-1;i>=0;--i){
18
            x=a[i];
19
            if (!flag) continue;
20
            if (s.empty()){s.push(x);continue;}
21
            while (x<s.top()){
22
                if (s.top()!=order){flag=false;break;}
23
                else{--order;s.pop();}
24
                if (s.empty()) break;
25
            }
26
            s.push(x);
27
        }
28
        if (!flag) printf("No\n");
29
        else printf("Yes\n");
30
    }
31
    return 0;
32
}

53 最长序列

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int a[5],dp1[5],dp2[5];
5
6
int main(){
7
    int T,ans;
8
    scanf("%d",&T);
9
    while (T--){
10
        ans=0;dp1[0]=1;dp2[0]=1;
11
        for (int i=0;i<5;++i){
12
            scanf("%d",&a[i]);
13
        }
14
        for (int i=1;i<5;++i){
15
            dp1[i]=1;dp2[i]=1;
16
            for (int j=0;j<i;++j){
17
                if (a[i]>a[j]) dp1[i]=max(1+dp1[j],dp1[i]);
18
                if (a[i]<a[j]) dp2[i]=max(1+dp2[j],dp2[i]);
19
            }
20
            ans=max(ans,max(dp1[i],dp2[i]));
21
        }
22
        printf("%d\n",ans);
23
    }
24
    return 0;
25
}

54 小偷偷东西

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int dp[505];
5
int v[50];
6
int w[50];
7
8
int main(){
9
    int n,c;
10
    int kase=0;
11
    while (~scanf("%d%d",&n,&c)){
12
        for (int i=1;i<=n;++i){
13
            scanf("%d",&v[i]);
14
        }
15
        for (int i=1;i<=n;++i){
16
            scanf("%d",&w[i]);
17
        }
18
        memset(dp,0,sizeof(dp));
19
        for (int i=1;i<=n;++i){
20
            for (int j=c;j>=w[i];--j){
21
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
22
            }
23
//            for (int j=0;j<=c;++j) printf("%d ",dp[j]);
24
//            putchar('\n');
25
        }
26
        printf("Case %d:%d\n",++kase,dp[c]);
27
    }
28
    return 0;
29
}

55 点在四边形内吗?

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
const double eps=1e-6;
4
#define zero(x) ((fabs(x)<eps?1:0))
5
#define sgn(x) (fabs(x)<eps?0:((x)<0?-1:1))
6
7
struct point{
8
    double x,y;
9
    point(double a=0,double b=0){x=a,y=b;}
10
    point operator-(const point& b)const{return point(x-b.x,y-b.y);}
11
    point operator+(const point& b)const{return point(x+b.x,y+b.y);}
12
    bool operator==(point& b){return zero(x-b.x)&&zero(y-b.y);}
13
    double operator*(const point& b)const{return x*b.x+y*b.y;}
14
    double operator^(const point& b)const{return x*b.y-y*b.x;}
15
};
16
struct line{
17
    point s,e;
18
    line(){}
19
    line(point ss,point ee){s=ss,e=ee;}
20
};
21
22
double dist(point a,point b){return sqrt((a-b)*(a-b));}
23
24
bool gao(point p,line l){
25
    return
26
        sgn((l.s-p)^(l.e-p))==0 &&
27
        sgn((p.x-l.s.x)*(p.x-l.e.x))<=0 &&
28
        sgn((p.y-l.s.y)*(p.y-l.e.y))<=0;
29
}
30
31
bool segxseg(line l1, line l2){
32
    return
33
        max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x) &&
34
        max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x) &&
35
        max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y) &&
36
        max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y) &&
37
        sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0 &&
38
        sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0;
39
}
40
41
int n;
42
point poly[1000];
43
int rua(point p){
44
    int cnt=0;
45
    line ray,side;
46
    ray.s=p;
47
    ray.e.y=p.y;
48
    ray.e.x=-100000000000.0;
49
    for (int i=0;i<n;++i){
50
        side.s=poly[i];
51
        side.e=poly[(i+1)%n];
52
        if (gao(p,side)) return 0;
53
        if (sgn(side.s.y-side.e.y)==0){
54
            continue;
55
        }
56
        if (gao(side.s,ray)){
57
            cnt+=(sgn(side.s.y-side.e.y)>0);
58
        }
59
        else if (gao(side.e,ray)){
60
            cnt+=(sgn(side.e.y-side.s.y)>0);
61
        }
62
        else if (segxseg(ray,side)) ++cnt;
63
    }
64
    return cnt%2==1?1:-1;
65
}
66
67
int main(){
68
    int T,kase=0;
69
    n=4;
70
    point tmp;
71
    scanf("%d",&T);
72
    while (T--){
73
        for (int i=0;i<4;++i){
74
            scanf("%lf%lf",&poly[i].x,&poly[i].y);
75
        }
76
        scanf("%lf%lf",&tmp.x,&tmp.y);
77
        printf("Case %d:\n%s\n",++kase,rua(tmp)==1?"In":"No");
78
//        cout<<rua(tmp)<<endl;
79
    }
80
    return 0;
81
}

57 点树

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define x first
4
#define y second
5
6
pair<int,int> a[105];
7
bool can[205][205];
8
9
inline int sgn(int x){
10
    if (x==0) return 0;
11
    return x/abs(x);
12
}
13
14
int gcd(int a,int b){
15
    return a==0?b:gcd(b%a,a);
16
}
17
18
int main(){
19
    int n,cur;
20
    int dx,dy;
21
    int curx,cury;
22
    while (~scanf("%d",&n)){
23
        memset(can,true,sizeof(can));
24
        for (int i=0;i<n;++i){
25
            scanf("%d%d",&a[i].x,&a[i].y);
26
            cur=gcd(a[i].x,a[i].y);
27
            dx=abs(a[i].x/cur)*sgn(a[i].x);
28
            dy=abs(a[i].y/cur)*sgn(a[i].y);
29
//            cout<<dx<<' '<<dy<<endl;
30
            curx=a[i].x+dx;cury=a[i].y+dy;
31
            while (abs(curx)<=100 && abs(cury)<=100){
32
                can[100+curx][100+cury]=false;
33
                curx+=dx;cury+=dy;
34
            }
35
        }
36
        cur=0;
37
        for (int i=0;i<n;++i){
38
            if (can[100+a[i].x][100+a[i].y]) ++cur;
39
        }
40
        printf("%d\n",cur);
41
    }
42
    return 0;
43
}

58 变量名转换

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
char a[50];
5
6
int main(){
7
    int T,kase=0;scanf("%d",&T);
8
    while (T--){
9
        scanf("%s",a);
10
        int len=strlen(a);
11
        bool flag=false;
12
        for (int i=0;i<len;++i){
13
            if (flag){
14
                if (a[i]>='a' && a[i]<='z'){
15
                    a[i]=a[i]-'a'+'A';
16
                    flag=false;
17
                }
18
                else if (a[i]>='A' && a[i]<='Z') flag=false;
19
            }
20
            else if (a[i]=='_') flag=true;
21
        }
22
        printf("Case %d:\n",++kase);
23
        for (int i=0;i<len;++i){
24
            if (a[i]!='_') putchar(a[i]);
25
        }
26
        putchar('\n');
27
    }
28
    return 0;
29
}

59 喊号子

Language: C++
Time: 4ms

1
#include <iostream>
2
#include <cstdio>
3
#include <string>
4
using namespace std;
5
int main(){
6
    string a="1-2-1 1-2-1 1 1 1-2-1";
7
    string b="1 2 3 4 1-2-3 4";
8
    int T,s,n;cin>>T;
9
    for (int i=1;i<=T;i++){
10
        cin>>n>>s;
11
        cout<<"Case "<<i<<":"<<endl;
12
        while (n--){
13
            if (s==1){
14
                s++;cout<<a<<endl;
15
            }
16
            else{
17
                s--;cout<<b<<endl;
18
            }
19
        }
20
    }
21
    return 0;
22
}

63 仓库管理员

Language: C++
Time: 136ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
5
struct node{
6
    mutable ll L,R;
7
    node(ll x,ll y):L(x),R(y){}
8
    bool operator < (const node &qmh) const{
9
        return L<qmh.L;
10
    }
11
};
12
13
set<node> kdl;
14
15
int main(){
16
    int T,n;
17
    ll x,t1,t2,t3,t4;
18
    char op[15];
19
    scanf("%d",&T);
20
    for (int kase=1;kase<=T;++kase){
21
        kdl.clear();
22
        kdl.insert((node){-1100000000,1100000000});
23
        scanf("%d",&n);
24
        printf("Case %d:\n",kase);
25
        while (n--){
26
            scanf("%s%lld",op,&x);
27
            if (op[0]=='F'){//down
28
                auto cur=kdl.upper_bound({x,0});
29
                --cur;
30
                if (x==(*cur).L){
31
                    printf("%lld\n",x);
32
                    if ((*cur).L!=(*cur).R){
33
                        ++(*cur).L;
34
                    }
35
                    else kdl.erase(cur);
36
                }
37
                else if (x<(*cur).R){
38
                    printf("%lld\n",x);
39
                    t1=(*cur).L,t2=x-1,t3=x+1,t4=(*cur).R;
40
                    kdl.erase(cur);
41
                    if (t1<=t2) kdl.insert({t1,t2});
42
                    if (t3<=t4) kdl.insert({t3,t4});
43
                }
44
                else{
45
                    printf("%lld\n",(*cur).R);
46
                    if ((*cur).L!=(*cur).R){
47
                        --(*cur).R;
48
                    }
49
                    else kdl.erase(cur);
50
                }
51
            }
52
            else{//up
53
                auto cur=kdl.upper_bound({x,0});
54
                --cur;
55
                if (x==(*cur).L){
56
                    printf("%lld\n",x);
57
                    if ((*cur).L!=(*cur).R){
58
                        ++(*cur).L;
59
                    }
60
                    else kdl.erase(cur);
61
                }
62
                else if (x<(*cur).R){
63
                    printf("%lld\n",x);
64
                    t1=(*cur).L,t2=x-1,t3=x+1,t4=(*cur).R;
65
                    kdl.erase(cur);
66
                    if (t1<=t2) kdl.insert({t1,t2});
67
                    if (t3<=t4) kdl.insert({t3,t4});
68
                }
69
                else if (x==(*cur).R){
70
                    printf("%lld\n",x);
71
                    if ((*cur).L!=(*cur).R){
72
                        --(*cur).R;
73
                    }
74
                    else kdl.erase(cur);
75
                }
76
                else{
77
                    ++cur;
78
                    printf("%lld\n",(*cur).L);
79
                    if ((*cur).L!=(*cur).R){
80
                        ++(*cur).L;
81
                    }
82
                    else kdl.erase(cur);
83
                }
84
            }
85
//            for (auto &i:kdl){
86
//                printf("[%lld,%lld]",i.L,i.R);
87
//            }
88
//            putchar('\n');
89
        }
90
    }
91
    return 0;
92
}

67 LCM

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
long long a[1005];
5
6
long long gcd(long long a, long long b){
7
    return a == 0 ? b : gcd(b % a, a);
8
}
9
10
int main(){
11
    int T,n;cin>>T;
12
    long long ans;
13
    while (T--){
14
        cin>>n;
15
        for (int i=0;i<n;++i){
16
            cin>>a[i];
17
        }
18
        if (n==1){
19
            cout<<a[0]<<endl;
20
            continue;
21
        }
22
        ans=a[0]*a[1]/gcd(a[0],a[1]);
23
        for (int i=2;i<n;++i){
24
            ans=ans*a[i]/gcd(ans,a[i]);
25
        }
26
        cout<<ans<<endl;
27
    }
28
    return 0;
29
}

69 Euchre Results

Language: C++
Time: 4ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int main(){
6
    int x1,x2,y1,y2,z1,z2;
7
    while (1){
8
        scanf("%d%d%d%d%d%d",&x1,&x2,&y1,&y2,&z1,&z2);
9
        if (x1+x2+y1+y2+z1+z2==0) break;
10
        int ans1=x1+x2;
11
        int ans2=x1+y1+z1-x2-y2-z2;
12
        printf("Anna's won-loss record is %d-%d.\n",(ans1-ans2)/2,(ans1+ans2)/2);
13
    }
14
    return 0;
15
}

71 合并果子

Language: C++
Time: 8ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
#include <string>
5
#include <cstring>
6
#include <algorithm>
7
#include <cmath>
8
#include <queue>
9
10
int main(){
11
    int n,temp,temp2,ans;
12
    while (~scanf("%d",&n)){
13
        priority_queue <int,vector<int>,greater<int> > que;
14
        while (!que.empty()) que.pop();
15
        for (int i=0;i<n;++i){
16
            scanf("%d",&temp);que.push(temp);
17
        }
18
        ans=0;
19
        while (que.size()>1){
20
            temp=que.top();que.pop();
21
            temp2=que.top();que.pop();
22
            ans+=temp+temp2;
23
//            cout<<temp+temp2<<' ';
24
            que.push(temp+temp2);
25
        }
26
        printf("%d\n",ans);
27
    }
28
    return 0;
29
}

72 yao哥鸡排系列之一——xyiyy的难题

Language: C++
Time: 8ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
ll gcd(ll a, ll b){
7
    return a==0?b:gcd(b%a,a);
8
}
9
10
ll lcm(ll a, ll b){
11
    return a/gcd(a,b)*b;
12
}
13
14
int a[20];
15
16
int main(){
17
    ll n,ans,lcmm;
18
    int m,cnt,cur;
19
    while (~scanf("%lld%d",&n,&m)){
20
        for (int i=0;i<m;++i){
21
            scanf("%d",&a[i]);
22
        }
23
        ans=0;
24
        for (int i=1;i<(1<<m);++i){
25
            cnt=(__builtin_popcount(i))%2==0?-1:1;
26
            lcmm=1;
27
            for (int j=0;j<m;++j){
28
                if (i&(1<<j)) lcmm=lcm(lcmm,a[j]);
29
            }
30
//            cout<<(bitset<10>)i<<": "<<cnt<<"*"<<n<<"/"<<lcmm<<endl;
31
            ans+=1ll*cnt*(n/lcmm);
32
        }
33
        printf("%lld\n",ans);
34
    }
35
    return 0;
36
}

76 yao哥鸡排系列之五——xyiyy的失策

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
char a[20];
5
bool flag;
6
int len;
7
8
void dfs(int p){
9
    if (p>=len){
10
        flag=true;
11
        return;
12
    }
13
    if (a[p]!='1') return;
14
    dfs(p+1);
15
    for (int i=1;i<=2 && flag==false && p+i<len;++i){
16
        if (a[p+i]!='8') break;
17
        dfs(p+i+1);
18
    }
19
}
20
21
int main(){
22
    int T;scanf("%d",&T);
23
    while (T--){
24
        flag=false;
25
        scanf("%s",a);
26
        len=strlen(a);
27
        for (int i=0;i<len;++i){
28
            if (a[i]!='1'&&a[i]!='8'){
29
                flag=true;
30
                break;
31
            }
32
        }
33
        if (flag){
34
            printf("NO\n");
35
            continue;
36
        }
37
        dfs(0);
38
        printf("%s\n",flag?"YES":"NO");
39
    }
40
    return 0;
41
}

78 yao哥鸡排系列之七——A+B problem

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int goal[25];
6
int main(){
7
    //FILE* fp;
8
    //fp=fopen("test.txt","w");
9
    int n;
10
    while (cin>>n){
11
        int x,y,z,sx=0,sy=0,sz=0;
12
        bool flag=true;
13
        for(int i=0;i<n;i++){
14
            cin>>x>>y>>z;
15
            goal[i]=5*x+10*y+20*z-15;       //第i个人期望得到的找零
16
            sx+=x;sy+=y;sz+=z;              //统计张数
17
            if (goal[i]<0){
18
                flag=false;
19
            }
20
        }
21
        if (!flag){
22
            cout<<"Angry Yaoge!"<<endl;
23
            //fprintf(fp,"Angry Yaoge!\n");
24
            continue;
25
        }
26
//        sx-=n;sy-=n;
27
//        if (sx<0||sy<0){
28
//            cout<<"Sad Yaoge!"<<endl;
29
//            continue;
30
//        }
31
        //20
32
        while(sz!=0){
33
            flag=true;
34
            for (int i=0;i<n;i++){
35
                if (goal[i]>=20){
36
                    goal[i]-=20;
37
                    sz--;
38
                    flag=false;
39
                    break;
40
                }
41
            }
42
            if (flag) break;
43
        }
44
        //10
45
        while(sy!=0){
46
            flag=true;
47
            for (int i=0;i<n;i++){
48
                if (goal[i]>=10){
49
                    goal[i]-=10;
50
                    sy--;
51
                    flag=false;
52
                    break;
53
                }
54
            }
55
            if (flag) break;
56
        }
57
        //5
58
        while(sx!=0){
59
            flag=true;
60
            for (int i=0;i<n;i++){
61
                if (goal[i]>=5){
62
                    goal[i]-=5;
63
                    sx--;
64
                    flag=false;
65
                    break;
66
                }
67
            }
68
            if (flag) break;
69
        }
70
71
72
        flag=true;
73
        for (int i=0;i<n;i++){
74
            if (goal[i]!=0){
75
                cout<<"Sad Yaoge!"<<endl;
76
                //fprintf(fp,"Sad Yaoge!\n");
77
                flag=false;
78
                break;
79
            }
80
        }
81
        if (flag) {
82
            cout<<"Happy Yaoge!"<<endl;
83
            //fprintf(fp,"Happy Yaoge!\n");
84
        }
85
    }
86
    return 0;
87
}

79 A1-行列式值

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
int main(){
4
    int a[3][3];
5
    for (int i=0;i<3;i++){
6
        for (int j=0;j<3;j++){
7
            cin>>a[i][j];
8
        }
9
    }
10
    cout<<a[0][0]*a[1][1]*a[2][2]\
11
         +a[0][1]*a[1][2]*a[2][0]\
12
         +a[0][2]*a[1][0]*a[2][1]\
13
         -a[0][0]*a[2][1]*a[1][2]\
14
         -a[0][1]*a[1][0]*a[2][2]\
15
         -a[0][2]*a[2][0]*a[1][1]<<endl;
16
    return 0;
17
}

80 A2-矩阵加法

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
int a[105][105];
4
int main(){
5
    int N;
6
    cin>>N;
7
    for (int i=0;i<N;i++){
8
        for (int j=0;j<N;j++){
9
            cin>>a[i][j];
10
        }
11
    }
12
    int x;
13
    for (int i=0;i<N;i++){
14
        for (int j=0;j<N;j++){
15
            cin>>x;
16
            a[i][j]+=x;
17
        }
18
    }
19
    for (int i=0;i<N;i++){
20
        for (int j=0;j<N;j++){
21
            cout<<a[i][j];
22
            if (j!=N-1) cout<<' ';
23
        }
24
        cout<<endl;
25
    }
26
    return 0;
27
}

81 A3-算术平均值和几何平均值

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    double a,b,c,d,e;
5
    cin>>a>>b>>c>>d>>e;
6
    double x = a * b * c * d * e;
7
    int f = ( x < 0)? -1 : 1;
8
    printf("%.2f, %.2f\n",(a+b+c+d+e)/5,f * pow(abs(x),0.2));
9
    return 0;
10
}

82 A4-十个整数排序

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
#include <cstdlib>
5
#include <algorithm>
6
using namespace std;
7
int main(){
8
    int a[10];
9
    for (int i=0;i<10;i++){
10
        cin>>a[i];
11
    }
12
    sort(a,a+10);
13
    for (int i=0;i<9;i++){
14
        cout<<a[i]<<' ';
15
    }
16
    cout<<a[9]<<endl;
17
    return 0;
18
}

83 A5-兑换钱币

Language: C++
Time: 4ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
int main(){
5
    int x,sum,I=1;
6
    while (cin>>x){
7
        sum=0;
8
        for (int i=0;i<=x/5;i++){
9
            for (int j=0;j<=(x-i*5)/2;j++){
10
                sum++;
11
            }
12
        }
13
        cout<<"Case "<<I++<<":"<<x<<","<<sum<<endl;
14
    }
15
    return 0;
16
}

84 A6-多项式计算

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cmath>
4
#include <cstdio>
5
6
int main(){
7
    int n;
8
    double x,t;
9
    while (cin>>n>>x){
10
        double sum=0;
11
        for (int i=n;i>=0;i--){
12
            cin>>t;
13
            sum+=t*pow(x,i);
14
        }
15
        printf("%.2f\n",sum);
16
    }
17
    return 0;
18
}

85 A7-多个a问题

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int main(){
6
    int n,a,bei;
7
    unsigned long long ans;
8
    while (cin>>n>>a){
9
        ans=0;bei=1;
10
        for (int i=0;i<=n;i++){
11
            ans+=bei*(n-i);
12
            bei*=10;
13
        }
14
        cout<<ans*a<<endl;
15
    }
16
    return 0;
17
}

86 A8-杨辉三角

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
char aa[27][300]=\
5
{"1",\
6
"1 1",\
7
"1 2 1",\
8
"1 3 3 1",\
9
"1 4 6 4 1",\
10
"1 5 10 10 5 1",\
11
"1 6 15 20 15 6 1",\
12
"1 7 21 35 35 21 7 1",\
13
"1 8 28 56 70 56 28 8 1",\
14
"1 9 36 84 126 126 84 36 9 1",\
15
"1 10 45 120 210 252 210 120 45 10 1",\
16
"1 11 55 165 330 462 462 330 165 55 11 1",\
17
"1 12 66 220 495 792 924 792 495 220 66 12 1",\
18
"1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1",\
19
"1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1",\
20
"1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1",\
21
"1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1",\
22
"1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1",\
23
"1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1",\
24
"1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1",\
25
"1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1",\
26
"1 21 210 1330 5985 20349 54264 116280 203490 293930 352716 352716 293930 203490 116280 54264 20349 5985 1330 210 21 1",\
27
"1 22 231 1540 7315 26334 74613 170544 319770 497420 646646 705432 646646 497420 319770 170544 74613 26334 7315 1540 231 22 1",\
28
"1 23 253 1771 8855 33649 100947 245157 490314 817190 1144066 1352078 1352078 1144066 817190 490314 245157 100947 33649 8855 1771 253 23 1",\
29
"1 24 276 2024 10626 42504 134596 346104 735471 1307504 1961256 2496144 2704156 2496144 1961256 1307504 735471 346104 134596 42504 10626 2024 276 24 1",\
30
"1 25 300 2300 12650 53130 177100 480700 1081575 2042975 3268760 4457400 5200300 5200300 4457400 3268760 2042975 1081575 480700 177100 53130 12650 2300 300 25 1"};
31
//static int a[26];
32
int main(){
33
//    cout<<"\"1\",\\"<<endl;
34
//    a[0]=1;
35
//    for (int j=1;j<=25;j++){
36
//        for (int i=25;i>0;i--){
37
//            a[i]+=a[i-1];
38
//        }
39
//        cout<<"\"";
40
//        for (int i=0;i<j;i++){
41
//            //if (!a[i]) break;
42
//            cout<<a[i]<<' ';
43
//        }
44
//        cout<<a[j]<<"\",\\"<<endl;
45
//    }
46
    int n,T=1;
47
    while (cin>>n){
48
        printf("Case %d: n=%d\n%s\n",T++,n,aa[n]);
49
    }
50
    return 0;
51
}

87 A9-百分制转换成五级分制

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
/*100~90    89~80   79~70   69~60   59~0*/
5
int main(){
6
    int T,x;
7
    cin>>T;
8
    while (T--){
9
        cin>>x;
10
        if (x>=90){
11
            cout<<"A"<<endl;
12
        }
13
        else if (x>=80){
14
            cout<<"B"<<endl;
15
        }
16
        else if (x>=70){
17
            cout<<"C"<<endl;
18
        }
19
        else if (x>=60){
20
            cout<<"D"<<endl;
21
        }
22
        else {
23
            cout<<"E"<<endl;
24
        }
25
    }
26
    return 0;
27
}

88 A10-Fibonacci数列

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
#include <string>
4
using namespace std;
5
int a[]={1,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903};
6
int main(){
7
//    int a[]={1,1};
8
//    cout<<"{1,1,";
9
//    for (int i=3;i<=47;i++){
10
//        a[1]+=a[0];
11
//        swap(a[0],a[1]);
12
//        cout<<a[1]<<',';
13
//    }
14
    int T=1,x;
15
    while (cin>>x){
16
        cout<<"Case "<<T++<<":"<<x<<","<<a[x]<<endl;
17
    }
18
    return 0;
19
}

89 A11-矩阵转置

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <algorithm>
4
#include <cmath>
5
#include <cstdio>
6
7
int a[100][100];
8
9
int main(){
10
    int m,n;
11
    while (cin>>m>>n){
12
        for (int i=0;i<m;i++){
13
            for (int j=0;j<n;j++){
14
                scanf("%d",&a[i][j]);
15
            }
16
        }
17
        for (int i=0;i<n;i++){
18
            for (int j=0;j<m-1;j++){
19
                printf("%d ",a[j][i]);
20
            }
21
            printf("%d\n",a[m-1][i]);
22
        }
23
        putchar('\n');
24
    }
25
    return 0;
26
}

90 A12-判断闰年

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int isrun(int x){
6
    if(x%4==0){
7
        if(x%100==0){
8
            if(x%400==0){
9
                return 1;
10
            }
11
            return 0;
12
        }
13
        return 1;
14
    }
15
    return 0;
16
}
17
18
int main(){
19
    int y;
20
    while (cin>>y){
21
        if (isrun(y)){
22
            printf("The year %d is a leap year.\n",y);
23
        }
24
        else{
25
            printf("The year %d is not a leap year.\n",y);
26
        }
27
    }
28
    return 0;
29
}

91 A13-求解一元二次方程

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
//    freopen("1.in","r", stdin);
6
//    freopen("11.out","w", stdout);
7
    double a,b,c;
8
    double ans1,ans2;
9
    while (cin>>a>>b>>c){
10
        ans1=(-b+sqrt(b*b-4*a*c))/2/a;
11
        ans2=(-b-sqrt(b*b-4*a*c))/2/a;
12
        if (ans1<ans2) swap(ans1,ans2);
13
//        cout<<ans1<<' '<<ans2<<endl;
14
        printf("%.2f %.2f\n",ans1,ans2);
15
    }
16
    return 0;
17
}

92 A14-去掉最高分去掉最低分

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
#include <algorithm>
4
using namespace std;
5
6
double a[10005];
7
8
int main(){
9
    int T,n;
10
    double ave;
11
    cin>>T;
12
    while (T--){
13
        scanf("%d",&n);
14
        for (int i=0;i<n;i++){
15
            scanf("%lf",&a[i]);
16
        }
17
        sort(a,a+n);
18
        ave=0;
19
        for (int i=1;i<n-1;i++){
20
            ave+=a[i];
21
        }
22
        printf("%.2f,%.2f,%.2f\n",a[0],a[n-1],ave/(n-2));
23
    }
24
    return 0;
25
}

93 A15-计算天数

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
using namespace std;
4
5
int isrun(int x){
6
    if(x%4==0){
7
        if(x%100==0){
8
            if(x%400==0){
9
                return 1;
10
            }
11
            return 0;
12
        }
13
        return 1;
14
    }
15
    return 0;
16
}
17
18
int a[13]={0,0,31,59,90,120,151,181,212,243,273,304,334};
19
int b[13]={0,0,31,60,91,121,152,182,213,244,274,305,335};
20
21
int main(){
22
    int T=1,yy,mm,dd;
23
    while (cin>>yy>>mm>>dd){
24
        printf("Case %d: %02d/%02d/%04d, ",T++,mm,dd,yy);
25
        if (isrun(yy)){
26
            printf("%d\n",b[mm]+dd);
27
        }
28
        else{
29
            printf("%d\n",a[mm]+dd);
30
        }
31
    }
32
    return 0;
33
}

95 A17-删除重复数据

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
int a[30005];
5
int main(){
6
    int i;
7
    while (cin>>a[0]){
8
        i=1;cout<<a[0];
9
        while (getchar()==' '){
10
            cin>>a[i];
11
            bool flag=true;
12
            for (int j=0;j<i;j++){
13
                if (a[i]==a[j]){
14
                    flag=false;
15
                    break;
16
                }
17
            }
18
            if(flag) cout<<' '<<a[i];
19
            i++;
20
        }
21
        printf("\n");
22
    }
23
    return 0;
24
}

96 A18-矩阵幂

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
5
const int maxn=10;
6
struct mat
7
{
8
    ll a[maxn][maxn];
9
    void init() {                         //初始化为单位矩阵
10
        memset(a, 0, sizeof(a));
11
        for (int i = 0; i<maxn; ++i) {
12
            a[i][i] = 1;
13
        }
14
    }
15
    void clear(){                     //清空矩阵
16
        memset(a, 0, sizeof(a));
17
    }
18
    mat operator *(const mat &b)const {  //重载乘法
19
        mat c; c.clear();
20
        for (int i = 0; i < maxn; i++)
21
            for (int j = 0; j < maxn; j++)
22
                for (int k = 0; k < maxn; k++)
23
                    c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]);
24
        return c;
25
    }
26
};
27
28
mat quick_pow(mat a, ll n)
29
{
30
    mat ans;
31
    ans.init();
32
    while (n)
33
    {
34
        if (n & 1)ans = ans*a;
35
        a = a*a;
36
        n >>= 1;
37
    }
38
    return ans;
39
}
40
41
int main(){
42
//    freopen("1.in","r", stdin);
43
//    freopen("1.out","w", stdout);
44
    mat a;
45
    ll n,k;
46
    bool flag=false;
47
    while (~scanf("%lld%lld",&n,&k)){
48
        if (flag) printf("\n\n");
49
        flag=true;
50
        a.clear();
51
        for (int i=0;i<n;++i){
52
            for (int j=0;j<n;++j){
53
                scanf("%lld",&a.a[i][j]);
54
            }
55
        }
56
        mat b=quick_pow(a,k);
57
        for (int i=0;i<n;++i){
58
            for (int j=0;j<n;++j){
59
                printf("%lld",b.a[i][j]);
60
                if (j!=n-1) putchar(' ');
61
            }
62
            if (i!=n-1) putchar('\n');
63
        }
64
    }
65
    return 0;
66
}

97 A19-逆时针螺旋方阵

Language: C++
Time: 8ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int a[110][110];
5
int d[4][2]={1,0,0,1,-1,0,0,-1};
6
7
int main(){
8
    int n;
9
    while(~scanf("%d",&n)){
10
        memset(a,-1,sizeof(a));
11
        int k=n*2,cnt=0,num=1,curx=0,cury=1;
12
        while (k/2!=0){
13
            for (int i=0;i<k/2;++i){
14
                curx+=d[cnt][0];
15
                cury+=d[cnt][1];
16
                a[curx][cury]=num++;
17
            }
18
            cnt=(cnt+1)%4;--k;
19
//            cout<<curx<<' '<<cury<<endl;
20
        }
21
        for (int  i=1;i<=n;++i){
22
            for (int j=1;j<=n;++j){
23
                printf("%d",a[i][j]);
24
                if (j!=n) putchar(' ');
25
            }
26
            putchar('\n');
27
        }
28
        putchar('\n');
29
    }
30
    return 0;
31
}

99 B1-字符串中转换小写字母

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
5
int main(){
6
    int T;
7
    char c;
8
    cin>>T;
9
    getchar();
10
    while (T--){
11
        while ((c=getchar())!='\n'){
12
            if (c>='a'&&c<='z') putchar(c-'a'+'A');
13
            else putchar(c);
14
        }
15
        putchar('\n');
16
    }
17
    return 0;
18
}

100 B2-空格字符与非空格字符统计

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
5
int main(){
6
    int T;
7
    char c;
8
    cin>>T;
9
    getchar();
10
    while (T--){
11
        int i=0,x=0,y=0;
12
        while ((c=getchar())!='\n'){
13
            if (c==' ') x++;
14
            else y++;
15
            i++;
16
        }
17
        printf("%d %d\n",y,x);
18
    }
19
    return 0;
20
}

101 B3-字符串倒置

Language: C++
Time: 1ms

1
#include <iostream>
2
using namespace std;
3
#include <cstdio>
4
char a[65546];
5
int main(){
6
    int T,kase=0;
7
    cin>>T;
8
    getchar();
9
    while (T--){
10
        int i=0;
11
        while ((a[i]=getchar())!='\n'){
12
            i++;
13
        }
14
        a[i]='\0';
15
        printf("Case %d: ",++kase);
16
        for (int j=i-1;j>=0;j--){
17
            putchar(a[j]);
18
        }
19
        putchar('\n');
20
    }
21
    return 0;
22
}

102 B4-统计单词

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int T;cin>>T;getchar();
5
    string a;
6
    for (int i=1;i<=T;i++){
7
        int n=0;
8
        getline(cin,a);
9
        stringstream b(a);
10
        string c;
11
        while (b>>c){
12
            n++;
13
        }
14
        cout<<"Case "<<i<<": "<<n<<endl;
15
    }
16
    return 0;
17
}

103 B5-分离整数

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    string s;
5
    char x;
6
    bool flag;
7
    int cnt,kase=0;
8
    while (getline(cin,s)){
9
        stringstream ss(s);
10
        flag=false;
11
        cnt=0;
12
        while (ss>>x){
13
            if (x>='0' && x<='9' && flag==false){
14
                cnt++;
15
                flag=true;
16
            }
17
            if ((x<'0'||x>'9') && flag==true){
18
                flag=false;
19
            }
20
        }
21
        cout<<"Case "<<++kase<<": "<<cnt<<endl;
22
    }
23
    return 0;
24
}

104 B6-统计子串

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
//KMP
5
int f[400009];
6
string a;
7
8
void getf(){
9
	int i=0,j=-1;
10
	f[0]=-1;
11
	while(i!=a.size()){
12
		if(j==-1||a[i]==a[j]) f[++i]=++j;
13
		else j=f[j];
14
	}
15
}
16
17
string b;
18
int main(){
19
    int kase=0;
20
    while (getline(cin,a)){
21
        getf();
22
//        cout<<a<<endl;
23
//        for (int i=1;i<=a.size();++i) cout<<f[i];
24
//        cout<<endl;
25
        getline(cin,b);
26
        int p=0,ans=0,lena=a.size(),lenb=b.size();
27
        while (p+lena<=lenb){
28
//            for (int i=0;i<p;++i) cout<<' ';
29
//            cout<<a<<endl;
30
            bool flag=true;
31
            int cnt;
32
            for (cnt=0;cnt<lena;++cnt){
33
                if (a[cnt]!=b[p+cnt]){
34
                    flag=false;
35
                    break;
36
                }
37
            }
38
            if (flag) ++ans;
39
            p=p+cnt-f[cnt];
40
        }
41
        printf("Case %d: %d\n",++kase,ans);
42
    }
43
    return 0;
44
}

105 B7-英文缩写词

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
string cur,s;
5
6
int main(){
7
    int kase=0,len;
8
    while (getline(cin,cur)){
9
        len=cur.length();
10
        for (int i=0;i<len;++i){
11
            if (cur[i]>='A' && cur[i]<='Z'){
12
                cur[i]=cur[i]-'A'+'a';
13
            }
14
            else if (cur[i]=='-') cur[i]=' ';
15
        }
16
        stringstream ss(cur);
17
        cout<<"Case "<<++kase<<": ";
18
        while (ss>>s){
19
            if (s!="a" && s!="an" && s!="the" && s!="of" && s!="for" && s!="and"){
20
                putchar(s[0]-'a'+'A');
21
            }
22
        }
23
        cout<<endl;
24
    }
25
    return 0;
26
}

106 B8-任意数制转换

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
5
void out(int x){
6
    if (x>=0&&x<=9){
7
        cout<<x;
8
        return;
9
    }
10
    putchar('A'+(x-10));
11
}
12
13
int main(){
14
    int x,n,kase=0;
15
    while (cin>>x>>n){
16
        cout<<"Case "<<++kase<<": ";
17
        int yinzi=1;
18
        while (yinzi*n<=x){
19
            yinzi*=n;
20
        }
21
//        cout<<yinzi<<endl;
22
//        system("pause");
23
        while (yinzi!=1){
24
//            cout<<x/yinzi<<' '<<yinzi<<endl;
25
//            system("pause");
26
            out(x/yinzi);
27
            x%=yinzi;
28
            yinzi/=n;
29
        }
30
        out(x);
31
        putchar('\n');
32
    }
33
}

107 B9-构造回文

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int T;cin>>T;getchar();
6
    string a,b;
7
    for (int kase=1;kase<=T;++kase){
8
        getline(cin,a);
9
        if (a.length()%2==0){
10
            b=a;
11
        }
12
        else{
13
            b=a.substr(0,a.size()-1);
14
        }
15
        reverse(b.begin(),b.end());
16
        cout<<"Case "<<kase<<": \""<<a+b<<"\"";
17
        if (kase!=T) cout<<endl;
18
    }
19
}

108 B10-加密

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
void encrypt(char x,int n){
5
    if (x>='a'&&x<='z'){
6
        x+=n;
7
        if (x>'z') x-=26;
8
    }
9
    else if (x>='A'&&x<='Z'){
10
        x+=n;
11
        if (x>'Z') x-=26;
12
    }
13
    putchar(x);
14
}
15
16
17
int main(){
18
    int n,m;
19
    char x;
20
    while (~scanf("%d%d",&n,&m)){
21
        getchar();
22
        for (int i=0;i<n;++i){
23
            x=getchar();
24
            encrypt(x,m);
25
        }
26
        putchar('\n');
27
    }
28
    return 0;
29
}

109 C1-阶乘尾部0的个数

Language: C++
Time: 1ms

1
#include <iostream>
2
#include <cstdio>
3
#include <cmath>
4
using namespace std;
5
int main(){
6
    int x,i=1;
7
    while (scanf("%d",&x)==1){
8
        printf("Case %d:%d,",i,x);
9
        int t=5,sum=0;
10
        while (t<=x){
11
            sum+=x/t;
12
            t*=5;
13
        }
14
        printf("%d\n",sum);
15
        i++;
16
    }
17
    return 0;
18
}

110 C2-n以内能被m整除的最大整数

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main(){
4
    int a,b,c,kase=0;
5
    while (~scanf("%d%d",&a,&b)){
6
        c=a-a%b;
7
        if (c>0 && c<=a) printf("Case %d: %d\n",++kase,c);
8
        else printf("Case %d: 不存在\n",++kase);
9
    }
10
    return 0;
11
}

112 C4-n以内与m互质的数的个数

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int gcd(int a,int b){
5
    return a == 0 ? b : gcd(b % a, a);
6
}
7
8
int main(){
9
    int n,m,kase=0,cnt;
10
    while (~scanf("%d%d",&n,&m)){
11
        cnt=0;
12
        for (int i=1;i<=n;++i){
13
            if (gcd(i,m)==1) ++cnt;
14
        }
15
        printf("Case %d: %d\n",++kase,cnt);
16
    }
17
    return 0;
18
}

113 C5-判断素数

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
//素数线性筛
5
const int N = 70000;
6
bool is[N];
7
int prime[N];
8
int cnt = 0;
9
10
void getprime(){
11
    memset(is, 1,sizeof(is));
12
    is[0] = is[1] = 0;
13
    for (int i = 2; i < N; ++i){
14
        if (is[i]) prime[++cnt] = i;
15
        for (int j = 1; j <= cnt && i*prime[j] < N; j++){
16
            is[i*prime[j]] = 0;
17
            if (!(i%prime[j])) break;
18
        }
19
    }
20
}
21
22
int main(){
23
    getprime();
24
    int n,kase=0;
25
    while (cin>>n){
26
        if (is[n]) cout<<"Case "<<++kase<<": "<<n<<" is a prime."<<endl;
27
        else cout<<"Case "<<++kase<<": "<<n<<" is not a prime."<<endl;
28
    }
29
    return 0;
30
}

114 C6-是否被11除尽

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int T;
6
    char x;
7
    scanf("%d%~c",&T);
8
    while (T--){
9
        int ans=0;
10
        while ((x=getchar())!='\n'){
11
            ans=(ans*10+x-'0')%11;
12
        }
13
        if (ans==0) printf("Yes\n");
14
        else printf("No\n");
15
    }
16
    return 0;
17
}

115 C7-是否被13除尽

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int T;
6
    char x;
7
    scanf("%d%~c",&T);
8
    while (T--){
9
        int ans=0;
10
        while ((x=getchar())!='\n'){
11
            ans=(ans*10+x-'0')%13;
12
        }
13
        if (ans==0) printf("Yes\n");
14
        else printf("No\n");
15
    }
16
    return 0;
17
}

116 C8-是否有整数解

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
//gcd 最大公约数
5
//欧几里得算法 辗转相除
6
long long gcd(long long a, long long b){
7
    return a == 0 ? b : gcd(b % a, a);
8
}
9
10
11
int main(){
12
    int T;
13
    long long a,b,c,d;
14
    scanf("%d",&T);
15
    while (T--){
16
        scanf("%lld%lld%lld",&a,&b,&c);
17
        a=a>0?a:-a;
18
        b=b>0?b:-b;
19
        c=c>0?c:-c;
20
        if (a==0 && b==0){
21
            printf("%s\n",c==0?"Yes":"No");
22
            continue;
23
        }
24
        if (a==0){
25
            printf("%s\n",c%b==0?"Yes":"No");
26
            continue;
27
        }
28
        if (b==0){
29
            printf("%s\n",c%a==0?"Yes":"No");
30
            continue;
31
        }
32
        d=gcd(a,b);
33
        if (c%d==0) printf("Yes\n");
34
        else printf("No\n");
35
    }
36
    return 0;
37
}

117 C9-百钱买百鸡

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int a,b,c,kase=0,sum;
6
    bool flag;
7
    while (~scanf("%d%d%d",&a,&b,&c)){
8
        printf("Case %d:\n",++kase);
9
        flag=true;
10
        for (int i=100;i>0 && flag;--i){
11
            for (int j=100;j>0;--j){
12
                int k=100-i-j;
13
                if (k<=1 || k%3!=0) continue;
14
                if (a*i+b*j+c*(k/3)!=100) continue;
15
                flag=false;
16
                printf("%d %d %d\n",i,j,k);
17
                break;
18
            }
19
        }
20
        if (flag) printf("Impossible\n");
21
    }
22
    return 0;
23
}

118 C10-Josephus问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
bool vis[110];
5
int nxt[110];
6
7
int main(){
8
    int n,m,p,pcnt,cnt;
9
    while (~scanf("%d%d",&n,&m)){
10
        memset(vis,false,sizeof(vis));
11
        for (int i=0;i<n;++i) scanf("%d",&nxt[i]);
12
        p=0;pcnt=m-1;cnt=n;
13
        while (cnt){
14
            while(pcnt){
15
                ++p;
16
                if (p==n) p=0;
17
                if (vis[p]) continue;
18
                --pcnt;
19
            }
20
            vis[p]=true;
21
            --cnt;
22
            pcnt=nxt[p];
23
//            for (int i=0;i<n;++i){
24
//                printf("%d ",vis[i]);
25
//            }
26
//            putchar('\n');
27
        }
28
        printf("%d\n",p+1);
29
    }
30
    return 0;
31
}

122 D3-整数分拆

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
5
ll cnt;
6
ll ans[]={0,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226,239943,281589,329931,386155,451276,526823,614154,715220,831820,966467,1121505,1300156,1505499,1741630,2012558,2323520,2679689,3087735,3554345,4087968,4697205,5392783,6185689,7089500,8118264,9289091,10619863,12132164,13848650,15796476,18004327,20506255,23338469,26543660,30167357,34262962,38887673,44108109,49995925,56634173,64112359,72533807,82010177,92669720,104651419,118114304,133230930,150198136,169229875,190569292,214481126,241265379,271248950,304801365,342325709,384276336,431149389,483502844,541946240,607163746,679903203,761002156,851376628,952050665,1064144451,1188908248,1327710076,1482074143,1653668665,1844349560};
7
8
9
void dfs(int x,int minn){
10
    if (x==0){++cnt; return;}
11
    for (int i=minn;i<=x;++i){
12
        dfs(x-i,i);
13
    }
14
}
15
16
int main(){
17
    int n;
18
    while (cin>>n){
19
        cout<<ans[n]<<endl;
20
    }
21
    return 0;
22
}

124 D5-“红色病毒”的变异

Language: C++
Time: 8ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
5
//快速幂
6
ll quick_pow(ll a, ll n){
7
    ll ans = 1;
8
    while (n){
9
        if (n & 1) ans = ans*a%100;  //若当前二进制位为1,则乘以a
10
        a = a*a%100;                          //此处的a实际为a^(2^t)
11
        n >>= 1;
12
    }
13
    return ans;
14
}
15
16
int main(){
17
    int T;
18
    while (scanf("%d",&T),T){
19
        int kase=0;
20
        long long x;
21
        while (T--){
22
            scanf("%lld",&x);
23
            printf("Case %d: %lld\n",++kase,quick_pow(4,x-1));
24
        }
25
        putchar('\n');
26
    }
27
}

125 D6-排坐

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
ll fac[30];
7
8
int main(){
9
    int n;
10
    ll ans;
11
    fac[0]=1;
12
    for (int i=1;i<=20;++i){
13
        fac[i]=fac[i-1]*i;
14
    }
15
    while (cin>>n){
16
        ans=fac[n-1]-4*fac[n-2]+2*fac[n-3];
17
        cout<<ans<<endl;
18
    }
19
    return 0;
20
}

126 D7-A+B问题

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
//简单大数模板
5
struct BigInt {                                   //新建一个结构体,用来模仿大数类
6
    const static int mod = 10000;
7
    const static int DLEN = 4;
8
    int a[100005],len;                               //长度
9
    BigInt(){
10
        memset(a,0,sizeof(a));                    //初始化
11
        len = 1;
12
    }
13
    BigInt(const char s[]){
14
        memset(a,0,sizeof(a));
15
        int L = strlen(s);
16
        len = L/DLEN;
17
        if(L%DLEN)
18
            len++;                                //将char数组转化为BigInt类型储存
19
        int index = 0;
20
        for(int i = L-1;i >= 0;i -= DLEN){
21
            int t = 0;
22
            int k = i - DLEN + 1;
23
            if(k < 0)k = 0;
24
            for(int j = k;j <= i;j++)
25
                t = t*10 + s[j] - '0';
26
            a[index++] = t;
27
        }
28
    }
29
    BigInt operator +(const BigInt &b)const{         //重构加法运算符
30
        BigInt res;
31
        res.len = max(len,b.len);
32
        for(int i = 0;i <= res.len;i++)
33
            res.a[i] = 0;
34
        for(int i = 0;i < res.len;i++){
35
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
36
            res.a[i+1] += res.a[i]/mod;
37
            res.a[i] %= mod;
38
        }
39
        if(res.a[res.len] > 0)
40
            res.len++;
41
        return res;
42
    }
43
    BigInt operator *(const BigInt &b)const{        //重构乘法运算符
44
        BigInt res;
45
        for(int i = 0; i < len;i++){
46
            int up = 0;
47
            for(int j = 0;j < b.len;j++){
48
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
49
                res.a[i+j] = temp%mod;
50
                up = temp/mod;
51
            }
52
            if(up != 0)
53
                res.a[i + b.len] = up;
54
        }
55
        res.len = len + b.len;
56
        while(res.a[res.len - 1] == 0 &&res.len > 1)
57
            res.len--;
58
        return res;
59
    }
60
    void output(){                              //由于没有输出的方式,添加输出的类
61
        printf("%d",a[len-1]);
62
        for(int i = len-2;i >=0 ;i--)
63
            printf("%04d",a[i]);
64
        //printf("\n");
65
    }
66
};
67
68
char a[10000],b[10000];
69
70
int main(){
71
    while(~scanf("%s%s",a,b)){
72
        BigInt aa=a;
73
        BigInt bb=b;
74
        BigInt cc=aa+bb;
75
        aa.output();
76
        putchar('+');
77
        bb.output();
78
        putchar('=');
79
        cc.output();
80
        putchar('\n');
81
    }
82
    return 0;
83
}

127 D8-A-B问题

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// base and base_digits must be consistent
5
constexpr int base = 1000000000;
6
constexpr int base_digits = 9;
7
8
struct bigint
9
{
10
    // value == 0 is represented by empty z
11
    vector<int> z; // digits
12
13
    // sign == 1 <==> value >= 0
14
    // sign == -1 <==> value < 0
15
    int sign;
16
17
    bigint() : sign(1) {}
18
19
    bigint(long long v) { *this = v; }
20
21
    bigint& operator=(long long v)
22
    {
23
        sign = v < 0 ? -1 : 1;
24
        v *= sign;
25
        z.clear();
26
        for (; v > 0; v = v / base)
27
            z.push_back((int)(v % base));
28
        return *this;
29
    }
30
31
    bigint(const string& s) { read(s); }
32
33
    bigint& operator+=(const bigint& other)
34
    {
35
        if (sign == other.sign)
36
        {
37
            for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
38
            {
39
                if (i == z.size())
40
                    z.push_back(0);
41
                z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
42
                carry = z[i] >= base;
43
                if (carry)
44
                    z[i] -= base;
45
            }
46
        }
47
        else if (other != 0 /* prevent infinite loop */)
48
        {
49
            *this -= -other;
50
        }
51
        return *this;
52
    }
53
54
    friend bigint operator+(bigint a, const bigint& b)
55
    {
56
        return a += b;
57
    }
58
59
    bigint& operator-=(const bigint& other)
60
    {
61
        if (sign == other.sign)
62
        {
63
            if (sign == 1 && *this >= other || sign == -1 && *this <= other)
64
            {
65
                for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
66
                {
67
                    z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
68
                    carry = z[i] < 0;
69
                    if (carry)
70
                        z[i] += base;
71
                }
72
                trim();
73
            }
74
            else
75
            {
76
                *this = other - *this;
77
                this->sign = -this->sign;
78
            }
79
        }
80
        else
81
        {
82
            *this += -other;
83
        }
84
        return *this;
85
    }
86
87
    friend bigint operator-(bigint a, const bigint& b)
88
    {
89
        return a -= b;
90
    }
91
92
    bigint& operator*=(int v)
93
    {
94
        if (v < 0)
95
            sign = -sign, v = -v;
96
        for (int i = 0, carry = 0; i < z.size() || carry; ++i)
97
        {
98
            if (i == z.size())
99
                z.push_back(0);
100
            long long cur = (long long)z[i] * v + carry;
101
            carry = (int)(cur / base);
102
            z[i] = (int)(cur % base);
103
        }
104
        trim();
105
        return *this;
106
    }
107
108
    bigint operator*(int v) const
109
    {
110
        return bigint(*this) *= v;
111
    }
112
113
    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1)
114
    {
115
        int norm = base / (b1.z.back() + 1);
116
        bigint a = a1.abs() * norm;
117
        bigint b = b1.abs() * norm;
118
        bigint q, r;
119
        q.z.resize(a.z.size());
120
121
        for (int i = (int)a.z.size() - 1; i >= 0; i--)
122
        {
123
            r *= base;
124
            r += a.z[i];
125
            int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
126
            int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
127
            int d = (int)(((long long)s1 * base + s2) / b.z.back());
128
            r -= b * d;
129
            while (r < 0)
130
                r += b, --d;
131
            q.z[i] = d;
132
        }
133
134
        q.sign = a1.sign * b1.sign;
135
        r.sign = a1.sign;
136
        q.trim();
137
        r.trim();
138
        return {q, r / norm};
139
    }
140
141
    friend bigint sqrt(const bigint& a1)
142
    {
143
        bigint a = a1;
144
        while (a.z.empty() || a.z.size() % 2 == 1)
145
            a.z.push_back(0);
146
147
        int n = a.z.size();
148
149
        int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
150
        int norm = base / (firstDigit + 1);
151
        a *= norm;
152
        a *= norm;
153
        while (a.z.empty() || a.z.size() % 2 == 1)
154
            a.z.push_back(0);
155
156
        bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
157
        firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
158
        int q = firstDigit;
159
        bigint res;
160
161
        for (int j = n / 2 - 1; j >= 0; j--)
162
        {
163
            for (;; --q)
164
            {
165
                bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
166
                if (r1 >= 0)
167
                {
168
                    r = r1;
169
                    break;
170
                }
171
            }
172
            res *= base;
173
            res += q;
174
175
            if (j > 0)
176
            {
177
                int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
178
                int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
179
                int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
180
                q = (int)(((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2));
181
            }
182
        }
183
184
        res.trim();
185
        return res / norm;
186
    }
187
188
    bigint operator/(const bigint& v) const
189
    {
190
        return divmod(*this, v).first;
191
    }
192
193
    bigint operator%(const bigint& v) const
194
    {
195
        return divmod(*this, v).second;
196
    }
197
198
    bigint& operator/=(int v)
199
    {
200
        if (v < 0)
201
            sign = -sign, v = -v;
202
        for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i)
203
        {
204
            long long cur = z[i] + rem * (long long)base;
205
            z[i] = (int)(cur / v);
206
            rem = (int)(cur % v);
207
        }
208
        trim();
209
        return *this;
210
    }
211
212
    bigint operator/(int v) const
213
    {
214
        return bigint(*this) /= v;
215
    }
216
217
    int operator%(int v) const
218
    {
219
        if (v < 0)
220
            v = -v;
221
        int m = 0;
222
        for (int i = (int)z.size() - 1; i >= 0; --i)
223
            m = (int)((z[i] + m * (long long)base) % v);
224
        return m * sign;
225
    }
226
227
    bigint& operator*=(const bigint& v)
228
    {
229
        *this = *this * v;
230
        return *this;
231
    }
232
233
    bigint& operator/=(const bigint& v)
234
    {
235
        *this = *this / v;
236
        return *this;
237
    }
238
239
    bool operator<(const bigint& v) const
240
    {
241
        if (sign != v.sign)
242
            return sign < v.sign;
243
        if (z.size() != v.z.size())
244
            return z.size() * sign < v.z.size() * v.sign;
245
        for (int i = (int)z.size() - 1; i >= 0; i--)
246
            if (z[i] != v.z[i])
247
                return z[i] * sign < v.z[i] * sign;
248
        return false;
249
    }
250
251
    bool operator>(const bigint& v) const
252
    {
253
        return v < *this;
254
    }
255
256
    bool operator<=(const bigint& v) const
257
    {
258
        return !(v < *this);
259
    }
260
261
    bool operator>=(const bigint& v) const
262
    {
263
        return !(*this < v);
264
    }
265
266
    bool operator==(const bigint& v) const
267
    {
268
        return !(*this < v) && !(v < *this);
269
    }
270
271
    bool operator!=(const bigint& v) const
272
    {
273
        return *this < v || v < *this;
274
    }
275
276
    void trim()
277
    {
278
        while (!z.empty() && z.back() == 0)
279
            z.pop_back();
280
        if (z.empty())
281
            sign = 1;
282
    }
283
284
    bool isZero() const
285
    {
286
        return z.empty();
287
    }
288
289
    friend bigint operator-(bigint v)
290
    {
291
        if (!v.z.empty())
292
            v.sign = -v.sign;
293
        return v;
294
    }
295
296
    bigint abs() const
297
    {
298
        return sign == 1 ? *this : -*this;
299
    }
300
301
    long long longValue() const
302
    {
303
        long long res = 0;
304
        for (int i = (int)z.size() - 1; i >= 0; i--)
305
            res = res * base + z[i];
306
        return res * sign;
307
    }
308
309
    friend bigint gcd(const bigint& a, const bigint& b)
310
    {
311
        return b.isZero() ? a : gcd(b, a % b);
312
    }
313
314
    friend bigint lcm(const bigint& a, const bigint& b)
315
    {
316
        return a / gcd(a, b) * b;
317
    }
318
319
    void read(const string& s)
320
    {
321
        sign = 1;
322
        z.clear();
323
        int pos = 0;
324
        while (pos < s.size() && (s[pos] == '-' || s[pos] == '+'))
325
        {
326
            if (s[pos] == '-')
327
                sign = -sign;
328
            ++pos;
329
        }
330
        for (int i = (int)s.size() - 1; i >= pos; i -= base_digits)
331
        {
332
            int x = 0;
333
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
334
                x = x * 10 + s[j] - '0';
335
            z.push_back(x);
336
        }
337
        trim();
338
    }
339
340
    friend istream& operator>>(istream& stream, bigint& v)
341
    {
342
        string s;
343
        stream >> s;
344
        v.read(s);
345
        return stream;
346
    }
347
348
    friend ostream& operator<<(ostream& stream, const bigint& v)
349
    {
350
        if (v.sign == -1)
351
            stream << '-';
352
        stream << (v.z.empty() ? 0 : v.z.back());
353
        for (int i = (int)v.z.size() - 2; i >= 0; --i)
354
            stream << setw(base_digits) << setfill('0') << v.z[i];
355
        return stream;
356
    }
357
358
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits)
359
    {
360
        vector<long long> p(max(old_digits, new_digits) + 1);
361
        p[0] = 1;
362
        for (int i = 1; i < p.size(); i++)
363
            p[i] = p[i - 1] * 10;
364
        vector<int> res;
365
        long long cur = 0;
366
        int cur_digits = 0;
367
        for (int v : a)
368
        {
369
            cur += v * p[cur_digits];
370
            cur_digits += old_digits;
371
            while (cur_digits >= new_digits)
372
            {
373
                res.push_back(int(cur % p[new_digits]));
374
                cur /= p[new_digits];
375
                cur_digits -= new_digits;
376
            }
377
        }
378
        res.push_back((int)cur);
379
        while (!res.empty() && res.back() == 0)
380
            res.pop_back();
381
        return res;
382
    }
383
384
    typedef vector<long long> vll;
385
386
    static vll karatsubaMultiply(const vll& a, const vll& b)
387
    {
388
        int n = a.size();
389
        vll res(n + n);
390
        if (n <= 32)
391
        {
392
            for (int i = 0; i < n; i++)
393
                for (int j = 0; j < n; j++)
394
                    res[i + j] += a[i] * b[j];
395
            return res;
396
        }
397
398
        int k = n >> 1;
399
        vll a1(a.begin(), a.begin() + k);
400
        vll a2(a.begin() + k, a.end());
401
        vll b1(b.begin(), b.begin() + k);
402
        vll b2(b.begin() + k, b.end());
403
404
        vll a1b1 = karatsubaMultiply(a1, b1);
405
        vll a2b2 = karatsubaMultiply(a2, b2);
406
407
        for (int i = 0; i < k; i++)
408
            a2[i] += a1[i];
409
        for (int i = 0; i < k; i++)
410
            b2[i] += b1[i];
411
412
        vll r = karatsubaMultiply(a2, b2);
413
        for (int i = 0; i < a1b1.size(); i++)
414
            r[i] -= a1b1[i];
415
        for (int i = 0; i < a2b2.size(); i++)
416
            r[i] -= a2b2[i];
417
418
        for (int i = 0; i < r.size(); i++)
419
            res[i + k] += r[i];
420
        for (int i = 0; i < a1b1.size(); i++)
421
            res[i] += a1b1[i];
422
        for (int i = 0; i < a2b2.size(); i++)
423
            res[i + n] += a2b2[i];
424
        return res;
425
    }
426
427
    bigint operator*(const bigint& v) const
428
    {
429
        vector<int> a6 = convert_base(this->z, base_digits, 6);
430
        vector<int> b6 = convert_base(v.z, base_digits, 6);
431
        vll a(a6.begin(), a6.end());
432
        vll b(b6.begin(), b6.end());
433
        while (a.size() < b.size())
434
            a.push_back(0);
435
        while (b.size() < a.size())
436
            b.push_back(0);
437
        while (a.size() & (a.size() - 1))
438
            a.push_back(0), b.push_back(0);
439
        vll c = karatsubaMultiply(a, b);
440
        bigint res;
441
        res.sign = sign * v.sign;
442
        for (int i = 0, carry = 0; i < c.size(); i++)
443
        {
444
            long long cur = c[i] + carry;
445
            res.z.push_back((int)(cur % 1000000));
446
            carry = (int)(cur / 1000000);
447
        }
448
        res.z = convert_base(res.z, 6, base_digits);
449
        res.trim();
450
        return res;
451
    }
452
};
453
454
int main()
455
{
456
    bigint a, b;
457
    int T;
458
    cin>>T;
459
    while (T--)
460
    {
461
        cin>>a>>b;
462
        cout<<a<<'-'<<b<<'='<<a-b<<endl;
463
    }
464
}

128 D9-n!

Language: C++
Time: 192ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
struct BigInt {                                   //新建一个结构体,用来模仿大数类
4
    const static int mod = 10000;
5
    const static int DLEN = 4;
6
    int a[100005],len;                               //长度
7
    BigInt(){
8
        memset(a,0,sizeof(a));                    //初始化
9
        len = 1;
10
    }
11
    BigInt(const char s[]){
12
        memset(a,0,sizeof(a));
13
        int L = strlen(s);
14
        len = L/DLEN;
15
        if(L%DLEN)
16
            len++;                                //将char数组转化为BigInt类型储存
17
        int index = 0;
18
        for(int i = L-1;i >= 0;i -= DLEN){
19
            int t = 0;
20
            int k = i - DLEN + 1;
21
            if(k < 0)k = 0;
22
            for(int j = k;j <= i;j++)
23
                t = t*10 + s[j] - '0';
24
            a[index++] = t;
25
        }
26
    }
27
    BigInt operator +(const BigInt &b)const{         //重构加法运算符
28
        BigInt res;
29
        res.len = max(len,b.len);
30
        for(int i = 0;i <= res.len;i++)
31
            res.a[i] = 0;
32
        for(int i = 0;i < res.len;i++){
33
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
34
            res.a[i+1] += res.a[i]/mod;
35
            res.a[i] %= mod;
36
        }
37
        if(res.a[res.len] > 0)
38
            res.len++;
39
        return res;
40
    }
41
    BigInt operator *(const BigInt &b)const{        //重构乘法运算符
42
        BigInt res;
43
        for(int i = 0; i < len;i++){
44
            int up = 0;
45
            for(int j = 0;j < b.len;j++){
46
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
47
                res.a[i+j] = temp%mod;
48
                up = temp/mod;
49
            }
50
            if(up != 0)
51
                res.a[i + b.len] = up;
52
        }
53
        res.len = len + b.len;
54
        while(res.a[res.len - 1] == 0 &&res.len > 1)
55
            res.len--;
56
        return res;
57
    }
58
    void output(){                              //由于没有输出的方式,添加输出的类
59
        printf("%d",a[len-1]);
60
        int cnt=log10(a[len-1])+1;
61
        for(int i = len-2;i >=0 ;i--){
62
            if (cnt==80){putchar('\n');cnt=0;}
63
            printf("%d",a[i]/1000);
64
            ++cnt;a[i]%=1000;
65
            if (cnt==80){putchar('\n');cnt=0;}
66
            printf("%d",a[i]/100);
67
            ++cnt;a[i]%=100;
68
            if (cnt==80){putchar('\n');cnt=0;}
69
            printf("%d",a[i]/10);
70
            ++cnt;a[i]%=10;
71
            if (cnt==80){putchar('\n');cnt=0;}
72
            printf("%d",a[i]);
73
            ++cnt;
74
        }
75
        if (cnt!=0) putchar('\n');
76
    }
77
};
78
79
80
int main(){
81
    int n;
82
    char tmp[]={'1','\0'};
83
    while (~scanf("%d",&n)){
84
        BigInt a=tmp,b=tmp,c=tmp;
85
        printf("%d!\n",n);
86
        for (int i=1;i<=n;++i){
87
            a=a*b;
88
            b=b+c;
89
        }
90
        a.output();
91
    }
92
    return 0;
93
}

129 D10-n的n次幂

Language: C++
Time: 96ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct BigInt {                                   //新建一个结构体,用来模仿大数类
5
    const static int mod = 10000;
6
    const static int DLEN = 4;
7
    int a[100005],len;                               //长度
8
    BigInt(){
9
        memset(a,0,sizeof(a));                    //初始化
10
        len = 1;
11
    }
12
    BigInt(const char s[]){
13
        memset(a,0,sizeof(a));
14
        int L = strlen(s);
15
        len = L/DLEN;
16
        if(L%DLEN)
17
            len++;                                //将char数组转化为BigInt类型储存
18
        int index = 0;
19
        for(int i = L-1;i >= 0;i -= DLEN){
20
            int t = 0;
21
            int k = i - DLEN + 1;
22
            if(k < 0)k = 0;
23
            for(int j = k;j <= i;j++)
24
                t = t*10 + s[j] - '0';
25
            a[index++] = t;
26
        }
27
    }
28
    BigInt operator +(const BigInt &b)const{         //重构加法运算符
29
        BigInt res;
30
        res.len = max(len,b.len);
31
        for(int i = 0;i <= res.len;i++)
32
            res.a[i] = 0;
33
        for(int i = 0;i < res.len;i++){
34
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
35
            res.a[i+1] += res.a[i]/mod;
36
            res.a[i] %= mod;
37
        }
38
        if(res.a[res.len] > 0)
39
            res.len++;
40
        return res;
41
    }
42
    BigInt operator *(const BigInt &b)const{        //重构乘法运算符
43
        BigInt res;
44
        for(int i = 0; i < len;i++){
45
            int up = 0;
46
            for(int j = 0;j < b.len;j++){
47
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
48
                res.a[i+j] = temp%mod;
49
                up = temp/mod;
50
            }
51
            if(up != 0)
52
                res.a[i + b.len] = up;
53
        }
54
        res.len = len + b.len;
55
        while(res.a[res.len - 1] == 0 &&res.len > 1)
56
            res.len--;
57
        return res;
58
    }
59
    void output(){                              //由于没有输出的方式,添加输出的类
60
        printf("%d",a[len-1]);
61
        for(int i = len-2;i >=0 ;i--)
62
            printf("%04d",a[i]);
63
        printf("\n");
64
    }
65
};
66
67
int main(){
68
    char x[10];
69
    while (~scanf("%s",x)){
70
        BigInt a=x,b=x;
71
        int xx=atoi(x);
72
        printf("%d^%d=\n",xx,xx);
73
        for (int i=1;i<xx;++i){
74
            a=a*b;
75
        }
76
        a.output();
77
    }
78
    return 0;
79
}

130 Yaoge is Good at Playing Army Chess

Language: C++
Time: 1ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
queue<int> q1,q2;
7
8
int main(){
9
    int n,m,cur;
10
    while (~scanf("%d%d",&n,&m)){
11
        while (!q1.empty()) q1.pop();
12
        while (!q2.empty()) q2.pop();
13
        while (n--){
14
            scanf("%d",&cur);
15
            q1.push(cur);
16
        }
17
        while (m--){
18
            scanf("%d",&cur);
19
            q2.push(cur);
20
        }
21
        while (true){
22
            if (q1.empty()&&q2.empty()){
23
                printf("Draw\n");
24
                break;
25
            }
26
            if (q1.empty()){
27
                printf("Second\n");
28
                break;
29
            }
30
            if (q2.empty()){
31
                printf("First\n");
32
                break;
33
            }
34
            if (q1.front()==31&&q2.front()==31){
35
                printf("Draw\n");
36
                break;
37
            }
38
            if (q1.front()==30 || q2.front()==30 || q1.front()==q2.front()){
39
                q1.pop();q2.pop();
40
            }
41
            else if (q1.front()==31){
42
                if (q2.front()==32) q1.pop();
43
                else q2.pop();
44
            }
45
            else if (q2.front()==31){
46
                if (q1.front()==32) q2.pop();
47
                else q1.pop();
48
            }
49
            else{
50
                if (q1.front()>q2.front()) q2.pop();
51
                else q1.pop();
52
            }
53
        }
54
    }
55
    return 0;
56
}

140 The Only Principle of Yaoge

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    char x;
6
    int status=0,ans=0;
7
    while ((x=getchar())!=EOF){
8
        if (x=='y' || x=='Y') status=1;
9
        else if ((x=='a' || x=='A') && status==1) status=2;
10
        else if ((x=='o' || x=='O') && status==2) status=3;
11
        else if ((x=='g' || x=='G') && status==3) status=4;
12
        else if ((x=='e' || x=='E') && status==4){
13
            ++ans;status=0;
14
        }
15
        else status=0;
16
    }
17
    printf("%d\n",ans);
18
    return 0;
19
}

146 XOR Zero

Language: C++
Time: 4ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
typedef long long ll;
5
6
int n;
7
ll num[110];
8
bool used[110];
9
10
void dbg(ll x){
11
    for (int i=63;i>=0;--i){
12
        printf("%d",(x&(1LL<<i))?1:0);
13
    }
14
    putchar('\n');
15
}
16
17
void Guass(){
18
    ll cur;int base;
19
    memset(used,false,sizeof(used));
20
    for (int p=1;p<=64;++p){
21
        cur=(1LL<<(64-p));
22
        base=-1;
23
        for (int i=1;i<=n;++i){
24
            if ((num[i]&cur)&&!used[i]){
25
                base=i;
26
                used[base]=true;
27
                break;
28
            }
29
        }
30
        if (base!=-1){
31
            for (int i=1;i<=n;++i){
32
                if ((num[i]&cur)&&i!=base)
33
                    num[i]^=num[base];
34
            }
35
        }
36
//        cout<<"term "<<p<<endl;
37
//        dbg(1LL<<(64-p));
38
//        cout<<"------------------------"<<endl;;
39
//        for (int i=1;i<=n;++i){
40
//            dbg(num[i]);
41
//        }
42
//        cout<<endl;
43
    }
44
}
45
46
int main(){
47
    bool flag;
48
    while (~scanf("%d",&n)){
49
        for (int i=1;i<=n;++i)
50
            scanf("%lld",&num[i]);
51
        if (n>=65){
52
            printf("YES\n");
53
            continue;
54
        }
55
        Guass();
56
        flag=false;
57
        for (int i=1;i<=n&&!flag;++i){
58
            if (num[i]==0) flag=true;
59
        }
60
        printf("%s\n",flag?"YES":"NO");
61
    }
62
    return 0;
63
}

149 找个数

Language: C++
Time: 248ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main(){
5
    int n,q,x;
6
    map <int,int> mmp;
7
    scanf("%d%d",&n,&q);
8
    while (n--){
9
        scanf("%d",&x);
10
        ++mmp[x];
11
    }
12
    while (q--){
13
        scanf("%d",&x);
14
        if (mmp[x]>0) printf("Yes\n");
15
        else printf("No\n");
16
    }
17
    return 0;
18
}

151 等级森严

Language: C++
Time: 44ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int fa[100100];
5
int rk[100100];
6
7
struct node{
8
    int fa,rk;
9
};
10
11
void init(int n){
12
    for (int i=1;i<=n;++i){
13
        fa[i]=i;
14
        rk[i]=0;
15
    }
16
}
17
18
node findfa(int x){
19
    if (fa[x]==x) return (node){x,0};
20
    node ret=findfa(fa[x]);
21
    fa[x]=ret.fa;
22
    rk[x]+=ret.rk;
23
    ret.rk=rk[x];
24
    return ret;
25
}
26
27
void merge(int x,int y){
28
    int fax=findfa(x).fa;
29
    int fay=findfa(y).fa;
30
    if (fax==fay) return;
31
    fa[fax]=y;
32
    rk[fax]=1;
33
}
34
35
node query(int x){
36
    return findfa(x);
37
}
38
39
40
int main(){
41
    int n,T,op,x,y;
42
    node a,b;
43
    scanf("%d%d",&n,&T);
44
    init(n);
45
    while (T--){
46
        scanf("%d%d%d",&op,&x,&y);
47
        if (op==1){
48
            merge(x,y);
49
        }
50
        else{
51
            a=query(x);
52
            b=query(y);
53
            if (a.fa!=b.fa) printf("No\n");
54
            else printf("Yes %d\n",b.rk-a.rk);
55
        }
56
    }
57
    return 0;
58
}

152 你个叛徒

Language: C++
Time: 48ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
const int maxn=3e5+1000;
5
6
int tmcnt;
7
int fa[maxn];
8
int pos[maxn];
9
10
void init(int n){
11
    for (int i=1;i<maxn;++i){
12
        fa[i]=pos[i]=i;
13
    }
14
    tmcnt=n;
15
}
16
17
int findfa(int x){
18
    if (x==fa[x]) return x;
19
    return x=findfa(fa[x]);
20
}
21
22
void merge(int x,int y){
23
    x=pos[x];
24
    y=pos[y];
25
    x=findfa(x);
26
    y=findfa(y);
27
    if (x==y) return;
28
    fa[x]=y;
29
    return;
30
}
31
32
bool query(int x,int y){
33
    x=pos[x];
34
    y=pos[y];
35
    x=findfa(x);
36
    y=findfa(y);
37
    return x==y;
38
}
39
40
void split(int x){
41
    pos[x]=tmcnt++;
42
    return;
43
}
44
45
int main(){
46
    int n,T,op,x,y;
47
    scanf("%d%d",&n,&T);
48
    init(n);
49
    while (T--){
50
        scanf("%d%d%d",&op,&x,&y);
51
        if (op==1){
52
            merge(x,y);
53
        }
54
        else if (op==2){
55
            if (query(x,y)) printf("Yes\n");
56
            else printf("No\n");
57
        }
58
        else{
59
            split(x);
60
            merge(x,y);
61
        }
62
    }
63
    return 0;
64
}

154 求个和

Language: C++
Time: 60ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
long long ans[100100];
5
6
int main(){
7
    int n,q,tmp,l,r;
8
    scanf("%d%d",&n,&q);
9
    ans[0]=0;
10
    for (int i=1;i<=n;++i){
11
        scanf("%d",&tmp);
12
        ans[i]=ans[i-1]+tmp;
13
    }
14
    while (q--){
15
        scanf("%d%d",&l,&r);
16
        printf("%lld\n",ans[r]-ans[l-1]);
17
    }
18
    return 0;
19
}

155 变个法地求个和

Language: C++
Time: 156ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
#define lson rt<<1
5
#define rson rt<<1|1
6
#define Lson L,mid,lson
7
#define Rson mid+1,R,rson
8
const int MAXN=100010;
9
10
ll tree[MAXN*4];
11
int lazy[MAXN*4];
12
13
void push_up(int rt){
14
    tree[rt]=tree[lson]+tree[rson];
15
}
16
17
void push_down(int rt,int len){
18
    if (lazy[rt]){
19
        lazy[lson]+=lazy[rt];
20
        lazy[rson]+=lazy[rt];
21
        tree[lson]+=lazy[rt]*(len-(len>>1));
22
        tree[rson]+=lazy[rt]*(len>>1);
23
        lazy[rt]=0;
24
    }
25
}
26
27
void build(int L,int R,int rt){
28
    lazy[rt]=0;
29
    if (L==R){
30
        scanf("%lld",&tree[rt]);
31
        return;
32
    }
33
    int mid=(L+R)>>1;
34
    build(Lson);
35
    build(Rson);
36
    push_up(rt);
37
}
38
39
void update(int l,int r,ll val,int L,int R,int rt){
40
    if (L>=l && R<=r){
41
        tree[rt]+=val*(R-L+1);
42
        lazy[rt]+=val;
43
        return;
44
    }
45
    push_down(rt,R-L+1);
46
    int mid=(L+R)>>1;
47
    if (mid>=l) update(l,r,val,Lson);
48
    if (mid<r) update(l,r,val,Rson);
49
    push_up(rt);
50
}
51
52
ll query(int l,int r,int L,int R,int rt){
53
    if (L>=l && R<=r){
54
        return tree[rt];
55
    }
56
    push_down(rt,R-L+1);
57
    ll ans=0;
58
    int mid=(L+R)>>1;
59
    if (mid>=l) ans+=query(l,r,Lson);
60
    if (mid<r) ans+=query(l,r,Rson);
61
    push_up(rt);
62
    return ans;
63
}
64
65
int main(){
66
    int n,q,op,l,r;
67
    ll v;
68
    scanf("%d%d",&n,&q);
69
    build(1,n,1);
70
    while (q--){
71
        scanf("%d",&op);
72
        if (op==1){
73
            scanf("%d%lld",&l,&v);
74
            update(l,l,v,1,n,1);
75
        }
76
        else if (op==2){
77
            scanf("%d%d",&l,&r);
78
            v=query(l,r,1,n,1);
79
            printf("%lld\n",v);
80
        }
81
    }
82
    return 0;
83
}

156 变着法地求个值

Language: C++
Time: 132ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
#define lson rt<<1
5
#define rson rt<<1|1
6
#define Lson L,mid,lson
7
#define Rson mid+1,R,rson
8
const int MAXN=100010;
9
10
ll tree[MAXN*4];
11
int lazy[MAXN*4];
12
13
void push_up(int rt){
14
    tree[rt]=tree[lson]+tree[rson];
15
}
16
17
void push_down(int rt,int len){
18
    if (lazy[rt]){
19
        lazy[lson]+=lazy[rt];
20
        lazy[rson]+=lazy[rt];
21
        tree[lson]+=lazy[rt]*(len-(len>>1));
22
        tree[rson]+=lazy[rt]*(len>>1);
23
        lazy[rt]=0;
24
    }
25
}
26
27
void build(int L,int R,int rt){
28
    lazy[rt]=0;
29
    if (L==R){
30
        scanf("%lld",&tree[rt]);
31
        return;
32
    }
33
    int mid=(L+R)>>1;
34
    build(Lson);
35
    build(Rson);
36
    push_up(rt);
37
}
38
39
void update(int l,int r,ll val,int L,int R,int rt){
40
    if (L>=l && R<=r){
41
        tree[rt]+=val*(R-L+1);
42
        lazy[rt]+=val;
43
        return;
44
    }
45
    push_down(rt,R-L+1);
46
    int mid=(L+R)>>1;
47
    if (mid>=l) update(l,r,val,Lson);
48
    if (mid<r) update(l,r,val,Rson);
49
    push_up(rt);
50
}
51
52
ll query(int p,int L,int R,int rt){
53
    if (L==R && L==p){
54
        return tree[rt];
55
    }
56
    push_down(rt,R-L+1);
57
    ll ans=0;
58
    int mid=(L+R)>>1;
59
    if (mid>=p) ans=query(p,Lson);
60
    else ans=query(p,Rson);
61
    push_up(rt);
62
    return ans;
63
}
64
65
int main(){
66
    int n,q,op,l,r;
67
    ll v;
68
    scanf("%d%d",&n,&q);
69
    build(1,n,1);
70
    while (q--){
71
        scanf("%d",&op);
72
        if (op==1){
73
            scanf("%d%d%lld",&l,&r,&v);
74
            update(l,r,v,1,n,1);
75
        }
76
        else if (op==2){
77
            scanf("%lld",&v);
78
            v=query(v,1,n,1);
79
            printf("%lld\n",v);
80
        }
81
    }
82
    return 0;
83
}

157 大和小

Language: C++
Time: 220ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
#define lson rt<<1
5
#define rson rt<<1|1
6
#define Lson L,mid,lson
7
#define Rson mid+1,R,rson
8
const int MAXN=100010;
9
10
ll t_max[MAXN*4];
11
ll t_min[MAXN*4];
12
ll tree[MAXN*4];
13
14
void push_up(int rt){
15
    tree[rt]=tree[lson]+tree[rson];
16
    t_max[rt]=max(t_max[lson],t_max[rson]);
17
    t_min[rt]=min(t_min[lson],t_min[rson]);
18
}
19
20
void build(int L,int R,int rt){
21
    if (L==R){
22
        scanf("%lld",&tree[rt]);
23
        t_max[rt]=tree[rt];
24
        t_min[rt]=tree[rt];
25
        return;
26
    }
27
    int mid=(L+R)>>1;
28
    build(Lson);
29
    build(Rson);
30
    push_up(rt);
31
}
32
33
void update(int p,ll val,int L,int R,int rt){
34
    if (L==R && L==p){
35
        tree[rt]+=val;
36
        t_max[rt]+=val;
37
        t_min[rt]+=val;
38
        return;
39
    }
40
    int mid=(L+R)>>1;
41
    if (mid>=p) update(p,val,Lson);
42
    if (mid<p) update(p,val,Rson);
43
    push_up(rt);
44
}
45
46
ll query_sum(int l,int r,int L,int R,int rt){
47
    if (L>=l && R<=r){
48
        return tree[rt];
49
    }
50
    ll ans=0;
51
    int mid=(L+R)>>1;
52
    if (mid>=l) ans+=query_sum(l,r,Lson);
53
    if (mid<r) ans+=query_sum(l,r,Rson);
54
    push_up(rt);
55
    return ans;
56
}
57
58
ll query_max(int l,int r,int L,int R,int rt){
59
    if (L>=l && R<=r){
60
        return t_max[rt];
61
    }
62
    ll ans=-1000000000000;
63
    int mid=(L+R)>>1;
64
    if (mid>=l) ans=max(ans,query_max(l,r,Lson));
65
    if (mid<r) ans=max(ans,query_max(l,r,Rson));
66
    push_up(rt);
67
    return ans;
68
}
69
70
ll query_min(int l,int r,int L,int R,int rt){
71
    if (L>=l && R<=r){
72
        return t_min[rt];
73
    }
74
    ll ans=1000000000000;
75
    int mid=(L+R)>>1;
76
    if (mid>=l) ans=min(ans,query_min(l,r,Lson));
77
    if (mid<r) ans=min(ans,query_min(l,r,Rson));
78
    push_up(rt);
79
    return ans;
80
}
81
int main(){
82
    int n,q,op,l,r;
83
    ll v;
84
    scanf("%d%d",&n,&q);
85
    build(1,n,1);
86
    while (q--){
87
        scanf("%d",&op);
88
        if (op==1){
89
            scanf("%d%lld",&l,&v);
90
            update(l,v,1,n,1);
91
        }
92
        else if (op==2){
93
            scanf("%d%d",&l,&r);
94
            v=query_max(l,r,1,n,1);
95
            printf("%lld ",v);
96
            v=query_sum(l,r,1,n,1);
97
            printf("%lld ",v);
98
            v=query_min(l,r,1,n,1);
99
            printf("%lld\n",v);
100
        }
101
    }
102
    return 0;
103
}

158 变着大法地求个和

Language: C++
Time: 160ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
#define lson rt<<1
5
#define rson rt<<1|1
6
#define Lson L,mid,lson
7
#define Rson mid+1,R,rson
8
const int MAXN=100010;
9
10
ll tree[MAXN*4];
11
ll lazy[MAXN*4];
12
13
void push_up(int rt){
14
    tree[rt]=tree[lson]+tree[rson];
15
}
16
17
void push_down(int rt,int len){
18
    if (lazy[rt]){
19
        lazy[lson]+=lazy[rt];
20
        lazy[rson]+=lazy[rt];
21
        tree[lson]+=lazy[rt]*(len-(len>>1));
22
        tree[rson]+=lazy[rt]*(len>>1);
23
        lazy[rt]=0;
24
    }
25
}
26
27
void build(int L,int R,int rt){
28
    lazy[rt]=0;
29
    if (L==R){
30
        scanf("%lld",&tree[rt]);
31
        return;
32
    }
33
    int mid=(L+R)>>1;
34
    build(Lson);
35
    build(Rson);
36
    push_up(rt);
37
}
38
39
void update(int l,int r,ll val,int L,int R,int rt){
40
    if (L>=l && R<=r){
41
        tree[rt]+=val*(R-L+1);
42
        lazy[rt]+=val;
43
        return;
44
    }
45
    push_down(rt,R-L+1);
46
    int mid=(L+R)>>1;
47
    if (mid>=l) update(l,r,val,Lson);
48
    if (mid<r) update(l,r,val,Rson);
49
    push_up(rt);
50
}
51
52
ll query(int l,int r,int L,int R,int rt){
53
    if (L>=l && R<=r){
54
        return tree[rt];
55
    }
56
    push_down(rt,R-L+1);
57
    ll ans=0;
58
    int mid=(L+R)>>1;
59
    if (mid>=l) ans+=query(l,r,Lson);
60
    if (mid<r) ans+=query(l,r,Rson);
61
    push_up(rt);
62
    return ans;
63
}
64
65
int main(){
66
    int n,q,op,l,r;
67
    ll v;
68
    scanf("%d%d",&n,&q);
69
    build(1,n,1);
70
    while (q--){
71
        scanf("%d",&op);
72
        if (op==1){
73
            scanf("%d%d%lld",&l,&r,&v);
74
            update(l,r,v,1,n,1);
75
        }
76
        else if (op==2){
77
            scanf("%d%d",&l,&r);
78
            v=query(l,r,1,n,1);
79
            printf("%lld\n",v);
80
        }
81
    }
82
    return 0;
83
}

159 线性变换地求个和

Language: C++
Time: 180ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
#define lson rt<<1
5
#define rson rt<<1|1
6
#define Lson L,mid,lson
7
#define Rson mid+1,R,rson
8
9
struct node{
10
    //变x*a+y , 不是x*(a+y)
11
    int x,y;
12
};
13
const int maxn=1e5+10;
14
15
//可改struct node
16
long long sum[maxn*4];
17
node lazy[maxn*4];
18
19
//更新完子节点pushup 后序递归
20
//维护的内容必须满足a[x,y]=a[x,i]某种操作a[i+1,y]
21
void pushup(int rt) {
22
    sum[rt]=sum[lson]+sum[rson];
23
}
24
25
//查改lson,rson点前pushdown rt 先序递归
26
//查改rt是不需要pushdown的
27
//所以叶子节点也有lazy更新但不可能用上
28
//仔细想想lazy是否有可叠加性
29
//lson长len-(len>>1),rson长len>>1
30
void pushdown(int rt,int len) {
31
    if(lazy[rt].x!=1 || lazy[rt].y!=0) {
32
//        cout<<"LAZY"<<endl;
33
        lazy[lson].x=lazy[lson].x*lazy[rt].x;
34
        lazy[lson].y=lazy[lson].y*lazy[rt].x+lazy[rt].y;
35
        lazy[rson].x=lazy[rson].x*lazy[rt].x;
36
        lazy[rson].y=lazy[rson].y*lazy[rt].x+lazy[rt].y;
37
        sum[lson]=sum[lson]*lazy[rt].x+lazy[rt].y*(len-(len>>1));
38
        sum[rson]=sum[rson]*lazy[rt].x+lazy[rt].y*(len>>1);
39
        lazy[rt].x=1;lazy[rt].y=0;
40
    }
41
}
42
43
//init
44
void build(int L,int R,int rt) {
45
    lazy[rt].x=1;
46
    lazy[rt].y=0;
47
    if(L==R) {
48
        scanf("%lld",&sum[rt]);
49
        return ;
50
    }
51
    int mid=(L+R)>>1;
52
    build(Lson);
53
    build(Rson);
54
    pushup(rt);
55
}
56
57
//板子是对的,错了是别的问题
58
void update(int l,int r,int val1,int val2,int L,int R,int rt) {
59
//    cout<<L<<' '<<R<<endl;
60
    if(l<=L&&r>=R) {
61
        sum[rt]=sum[rt]*val1+(R-L+1)*val2;
62
        lazy[rt].x=lazy[rt].x*val1;
63
        lazy[rt].y=lazy[rt].y*val1+val2;
64
        return;
65
    }
66
    pushdown(rt,R-L+1);
67
    int mid=(L+R)>>1;
68
    if(l<=mid)
69
        update(l,r,val1,val2,Lson);
70
    if(r>mid)
71
        update(l,r,val1,val2,Rson);
72
    pushup(rt);
73
}
74
75
//板子是对的,错了是别的问题
76
long long query(int l,int r,int L,int R,int rt) {
77
    if(l<=L&&r>=R) {
78
        return sum[rt];
79
    }
80
    pushdown(rt,R-L+1);
81
    int mid=(L+R)>>1;
82
    long long res=0;
83
    if(l<=mid)
84
        res+=query(l,r,Lson);
85
    if(r>mid)
86
        res+=query(l,r,Rson);
87
    return res;
88
}
89
90
int N,Q,op;
91
92
int main() {
93
    while(~scanf("%d%d",&N,&Q)) {
94
        build(1,N,1);
95
        while(Q--) {
96
            scanf("%d",&op);
97
            if(op==1) {
98
                int l,r;
99
                int x1,x2;
100
                scanf("%d%d%d%d",&l,&r,&x1,&x2);
101
                update(l,r,x1,x2,1,N,1);
102
            }
103
            else {
104
                int l,r;
105
                scanf("%d%d",&l,&r);
106
                printf("%lld\n",query(l,r,1,N,1));
107
            }
108
        }
109
    }
110
    return 0;
111
}

164 Multiplification

Language: C++
Time: 292ms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// base and base_digits must be consistent
5
constexpr int base = 1000000000;
6
constexpr int base_digits = 9;
7
8
struct bigint
9
{
10
    // value == 0 is represented by empty z
11
    vector<int> z; // digits
12
13
    // sign == 1 <==> value >= 0
14
    // sign == -1 <==> value < 0
15
    int sign;
16
17
    bigint() : sign(1) {}
18
19
    bigint(long long v) { *this = v; }
20
21
    bigint& operator=(long long v)
22
    {
23
        sign = v < 0 ? -1 : 1;
24
        v *= sign;
25
        z.clear();
26
        for (; v > 0; v = v / base)
27
            z.push_back((int)(v % base));
28
        return *this;
29
    }
30
31
    bigint(const string& s) { read(s); }
32
33
    bigint& operator+=(const bigint& other)
34
    {
35
        if (sign == other.sign)
36
        {
37
            for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
38
            {
39
                if (i == z.size())
40
                    z.push_back(0);
41
                z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
42
                carry = z[i] >= base;
43
                if (carry)
44
                    z[i] -= base;
45
            }
46
        }
47
        else if (other != 0 /* prevent infinite loop */)
48
        {
49
            *this -= -other;
50
        }
51
        return *this;
52
    }
53
54
    friend bigint operator+(bigint a, const bigint& b)
55
    {
56
        return a += b;
57
    }
58
59
    bigint& operator-=(const bigint& other)
60
    {
61
        if (sign == other.sign)
62
        {
63
            if (sign == 1 && *this >= other || sign == -1 && *this <= other)
64
            {
65
                for (int i = 0, carry = 0; i < other.z.size() || carry; ++i)
66
                {
67
                    z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
68
                    carry = z[i] < 0;
69
                    if (carry)
70
                        z[i] += base;
71
                }
72
                trim();
73
            }
74
            else
75
            {
76
                *this = other - *this;
77
                this->sign = -this->sign;
78
            }
79
        }
80
        else
81
        {
82
            *this += -other;
83
        }
84
        return *this;
85
    }
86
87
    friend bigint operator-(bigint a, const bigint& b)
88
    {
89
        return a -= b;
90
    }
91
92
    bigint& operator*=(int v)
93
    {
94
        if (v < 0)
95
            sign = -sign, v = -v;
96
        for (int i = 0, carry = 0; i < z.size() || carry; ++i)
97
        {
98
            if (i == z.size())
99
                z.push_back(0);
100
            long long cur = (long long)z[i] * v + carry;
101
            carry = (int)(cur / base);
102
            z[i] = (int)(cur % base);
103
        }
104
        trim();
105
        return *this;
106
    }
107
108
    bigint operator*(int v) const
109
    {
110
        return bigint(*this) *= v;
111
    }
112
113
    friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1)
114
    {
115
        int norm = base / (b1.z.back() + 1);
116
        bigint a = a1.abs() * norm;
117
        bigint b = b1.abs() * norm;
118
        bigint q, r;
119
        q.z.resize(a.z.size());
120
121
        for (int i = (int)a.z.size() - 1; i >= 0; i--)
122
        {
123
            r *= base;
124
            r += a.z[i];
125
            int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
126
            int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
127
            int d = (int)(((long long)s1 * base + s2) / b.z.back());
128
            r -= b * d;
129
            while (r < 0)
130
                r += b, --d;
131
            q.z[i] = d;
132
        }
133
134
        q.sign = a1.sign * b1.sign;
135
        r.sign = a1.sign;
136
        q.trim();
137
        r.trim();
138
        return {q, r / norm};
139
    }
140
141
    friend bigint sqrt(const bigint& a1)
142
    {
143
        bigint a = a1;
144
        while (a.z.empty() || a.z.size() % 2 == 1)
145
            a.z.push_back(0);
146
147
        int n = a.z.size();
148
149
        int firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
150
        int norm = base / (firstDigit + 1);
151
        a *= norm;
152
        a *= norm;
153
        while (a.z.empty() || a.z.size() % 2 == 1)
154
            a.z.push_back(0);
155
156
        bigint r = (long long)a.z[n - 1] * base + a.z[n - 2];
157
        firstDigit = (int)::sqrt((double)a.z[n - 1] * base + a.z[n - 2]);
158
        int q = firstDigit;
159
        bigint res;
160
161
        for (int j = n / 2 - 1; j >= 0; j--)
162
        {
163
            for (;; --q)
164
            {
165
                bigint r1 = (r - (res * 2 * base + q) * q) * base * base + (j > 0 ? (long long)a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
166
                if (r1 >= 0)
167
                {
168
                    r = r1;
169
                    break;
170
                }
171
            }
172
            res *= base;
173
            res += q;
174
175
            if (j > 0)
176
            {
177
                int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
178
                int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
179
                int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
180
                q = (int)(((long long)d1 * base * base + (long long)d2 * base + d3) / (firstDigit * 2));
181
            }
182
        }
183
184
        res.trim();
185
        return res / norm;
186
    }
187
188
    bigint operator/(const bigint& v) const
189
    {
190
        return divmod(*this, v).first;
191
    }
192
193
    bigint operator%(const bigint& v) const
194
    {
195
        return divmod(*this, v).second;
196
    }
197
198
    bigint& operator/=(int v)
199
    {
200
        if (v < 0)
201
            sign = -sign, v = -v;
202
        for (int i = (int)z.size() - 1, rem = 0; i >= 0; --i)
203
        {
204
            long long cur = z[i] + rem * (long long)base;
205
            z[i] = (int)(cur / v);
206
            rem = (int)(cur % v);
207
        }
208
        trim();
209
        return *this;
210
    }
211
212
    bigint operator/(int v) const
213
    {
214
        return bigint(*this) /= v;
215
    }
216
217
    int operator%(int v) const
218
    {
219
        if (v < 0)
220
            v = -v;
221
        int m = 0;
222
        for (int i = (int)z.size() - 1; i >= 0; --i)
223
            m = (int)((z[i] + m * (long long)base) % v);
224
        return m * sign;
225
    }
226
227
    bigint& operator*=(const bigint& v)
228
    {
229
        *this = *this * v;
230
        return *this;
231
    }
232
233
    bigint& operator/=(const bigint& v)
234
    {
235
        *this = *this / v;
236
        return *this;
237
    }
238
239
    bool operator<(const bigint& v) const
240
    {
241
        if (sign != v.sign)
242
            return sign < v.sign;
243
        if (z.size() != v.z.size())
244
            return z.size() * sign < v.z.size() * v.sign;
245
        for (int i = (int)z.size() - 1; i >= 0; i--)
246
            if (z[i] != v.z[i])
247
                return z[i] * sign < v.z[i] * sign;
248
        return false;
249
    }
250
251
    bool operator>(const bigint& v) const
252
    {
253
        return v < *this;
254
    }
255
256
    bool operator<=(const bigint& v) const
257
    {
258
        return !(v < *this);
259
    }
260
261
    bool operator>=(const bigint& v) const
262
    {
263
        return !(*this < v);
264
    }
265
266
    bool operator==(const bigint& v) const
267
    {
268
        return !(*this < v) && !(v < *this);
269
    }
270
271
    bool operator!=(const bigint& v) const
272
    {
273
        return *this < v || v < *this;
274
    }
275
276
    void trim()
277
    {
278
        while (!z.empty() && z.back() == 0)
279
            z.pop_back();
280
        if (z.empty())
281
            sign = 1;
282
    }
283
284
    bool isZero() const
285
    {
286
        return z.empty();
287
    }
288
289
    friend bigint operator-(bigint v)
290
    {
291
        if (!v.z.empty())
292
            v.sign = -v.sign;
293
        return v;
294
    }
295
296
    bigint abs() const
297
    {
298
        return sign == 1 ? *this : -*this;
299
    }
300
301
    long long longValue() const
302
    {
303
        long long res = 0;
304
        for (int i = (int)z.size() - 1; i >= 0; i--)
305
            res = res * base + z[i];
306
        return res * sign;
307
    }
308
309
    friend bigint gcd(const bigint& a, const bigint& b)
310
    {
311
        return b.isZero() ? a : gcd(b, a % b);
312
    }
313
314
    friend bigint lcm(const bigint& a, const bigint& b)
315
    {
316
        return a / gcd(a, b) * b;
317
    }
318
319
    void read(const string& s)
320
    {
321
        sign = 1;
322
        z.clear();
323
        int pos = 0;
324
        while (pos < s.size() && (s[pos] == '-' || s[pos] == '+'))
325
        {
326
            if (s[pos] == '-')
327
                sign = -sign;
328
            ++pos;
329
        }
330
        for (int i = (int)s.size() - 1; i >= pos; i -= base_digits)
331
        {
332
            int x = 0;
333
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
334
                x = x * 10 + s[j] - '0';
335
            z.push_back(x);
336
        }
337
        trim();
338
    }
339
340
    friend istream& operator>>(istream& stream, bigint& v)
341
    {
342
        string s;
343
        stream >> s;
344
        v.read(s);
345
        return stream;
346
    }
347
348
    friend ostream& operator<<(ostream& stream, const bigint& v)
349
    {
350
        if (v.sign == -1)
351
            stream << '-';
352
        stream << (v.z.empty() ? 0 : v.z.back());
353
        for (int i = (int)v.z.size() - 2; i >= 0; --i)
354
            stream << setw(base_digits) << setfill('0') << v.z[i];
355
        return stream;
356
    }
357
358
    static vector<int> convert_base(const vector<int>& a, int old_digits, int new_digits)
359
    {
360
        vector<long long> p(max(old_digits, new_digits) + 1);
361
        p[0] = 1;
362
        for (int i = 1; i < p.size(); i++)
363
            p[i] = p[i - 1] * 10;
364
        vector<int> res;
365
        long long cur = 0;
366
        int cur_digits = 0;
367
        for (int v : a)
368
        {
369
            cur += v * p[cur_digits];
370
            cur_digits += old_digits;
371
            while (cur_digits >= new_digits)
372
            {
373
                res.push_back(int(cur % p[new_digits]));
374
                cur /= p[new_digits];
375
                cur_digits -= new_digits;
376
            }
377
        }
378
        res.push_back((int)cur);
379
        while (!res.empty() && res.back() == 0)
380
            res.pop_back();
381
        return res;
382
    }
383
384
    typedef vector<long long> vll;
385
386
    static vll karatsubaMultiply(const vll& a, const vll& b)
387
    {
388
        int n = a.size();
389
        vll res(n + n);
390
        if (n <= 32)
391
        {
392
            for (int i = 0; i < n; i++)
393
                for (int j = 0; j < n; j++)
394
                    res[i + j] += a[i] * b[j];
395
            return res;
396
        }
397
398
        int k = n >> 1;
399
        vll a1(a.begin(), a.begin() + k);
400
        vll a2(a.begin() + k, a.end());
401
        vll b1(b.begin(), b.begin() + k);
402
        vll b2(b.begin() + k, b.end());
403
404
        vll a1b1 = karatsubaMultiply(a1, b1);
405
        vll a2b2 = karatsubaMultiply(a2, b2);
406
407
        for (int i = 0; i < k; i++)
408
            a2[i] += a1[i];
409
        for (int i = 0; i < k; i++)
410
            b2[i] += b1[i];
411
412
        vll r = karatsubaMultiply(a2, b2);
413
        for (int i = 0; i < a1b1.size(); i++)
414
            r[i] -= a1b1[i];
415
        for (int i = 0; i < a2b2.size(); i++)
416
            r[i] -= a2b2[i];
417
418
        for (int i = 0; i < r.size(); i++)
419
            res[i + k] += r[i];
420
        for (int i = 0; i < a1b1.size(); i++)
421
            res[i] += a1b1[i];
422
        for (int i = 0; i < a2b2.size(); i++)
423
            res[i + n] += a2b2[i];
424
        return res;
425
    }
426
427
    bigint operator*(const bigint& v) const
428
    {
429
        vector<int> a6 = convert_base(this->z, base_digits, 6);
430
        vector<int> b6 = convert_base(v.z, base_digits, 6);
431
        vll a(a6.begin(), a6.end());
432
        vll b(b6.begin(), b6.end());
433
        while (a.size() < b.size())
434
            a.push_back(0);
435
        while (b.size() < a.size())
436
            b.push_back(0);
437
        while (a.size() & (a.size() - 1))
438
            a.push_back(0), b.push_back(0);
439
        vll c = karatsubaMultiply(a, b);
440
        bigint res;
441
        res.sign = sign * v.sign;
442
        for (int i = 0, carry = 0; i < c.size(); i++)
443
        {
444
            long long cur = c[i] + carry;
445
            res.z.push_back((int)(cur % 1000000));
446
            carry = (int)(cur / 1000000);
447
        }
448
        res.z = convert_base(res.z, 6, base_digits);
449
        res.trim();
450
        return res;
451
    }
452
};
453
454
int main()
455
{
456
    bigint a, b;
457
    int T;
458
    cin>>T;
459
    while (T--)
460
    {
461
        cin>>a>>b;
462
        cout<<a*b<<endl;
463
    }
464
}

171 小6的灾难

Language: C++
Time: 120ms

1