考场拼命$yy$高精度结果没学好$for$循环痛失$50pts$，当场枯死
以后一定打对拍，要不考后会。。。
T1 石子游戏
首先要知道典型的$NIM$博弈，就是说如果所有堆石子个数的异或和为$0$则先手必输
那么这道题给出了取石子上限，那么每堆石子$\mod x+1$然后异或就可以知道谁必胜了
然后这道题就转化为如何求$\sum \limits_{i=1}^{n}\oplus a_i \mod(x+1)$。
分段考虑每一段$[k(x+1),(k+1)(x+1)]$，然后预处理一个$f$数组
T2 大鱼吃小鱼
直接$multiset$水四十
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=3e5+5;
15 int n,w[NN],q,stk[NN],top;
16 multiset<int> s;
17 #define sit multiset<int>::iterator
18 namespace WSN{
19 inline short main(){
20 // freopen("in.in","r",stdin); freopen("sb.out","w",stdout);
21 freopen("fish.in","r",stdin);
22 freopen("fish.out","w",stdout);
23 n=read();for(int i=1;i<=n;i++) w[i]=read(),s.insert(w[i]);
24 q=read();int tim=0;
25 while(q--){
26 int opt=read();++tim;
27 if(opt==1){
28 int st=read(),k=read(),ans=0,flag=0;
29 if(st>=k){write(0);continue;}
30 top=0;
31 while(s.size()){
32 sit it=s.upper_bound(st-1);
33 if(it!=s.begin()) --it;
34 else {flag=1;break;}
35 st+=*it; s.erase(it); stk[++top]=*it;
36 ++ans;
37 if(st>=k) break;
38 }
39 while(top) s.insert(stk[top--]);
40 if(flag||st<k){puts("-1");continue;}
41 write(ans);
42 }
43 if(opt==2){
44 int v=read();s.insert(v);
45 }
46 if(opt==3){
47 int v=read();s.erase(s.find(v));
48 }
49 }
50 return 0;
51 }
52 }
53 signed main(){return WSN::main();}
TLE40
T3 黑客
考场上没写出来的大水数论题，就是五分钟打了暴力就跑，没考虑正解（暴力分太高）
枚举分数算倍数个数就行
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(register int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int mod=1e9+7;
15 int A,B,C,D,ans;
16 inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
17 inline int mo(int x){return x>=mod?x-mod:x;}
18 namespace WSN{
19 inline short main(){
20 freopen("hacker.in","r",stdin);
21 freopen("hacker.out","w",stdout);
22 A=read();B=read();C=read();D=read();
23 for(int i=1;i<=999;i++)
24 for(int j=1;j<=999-i;j++) if(gcd(i,j)==1){
25 int l1=ceil(1.0*A/i),r1=B/i;
26 int l2=ceil(1.0*C/j),r2=D/j;
27 int a=min(r1,r2),b=max(l1,l2);
28 if(a-b+1>0) ans=mo(ans+(i+j)*((a-b+1)%mod)%mod);
29 } write(ans);
30 return 0;
31 }
32 }
33 signed main(){return WSN::main();}
View Code
T4 黑客（续）
珍爱生命，远离高精
$m=0$加暴力可以获得$70pts$可是考场上没读明白那个限制条件就只打了$m=0$还打挂了
就爆零了，非常难受，以后还事能重载运算符就重载吧，要不一遍一遍的打太容易错
就是一个普通的数位$dp$套高精度，压位高精度到$17$位刚刚好，如果特判$m=0$会更快
$f[pos][sta]$表示$dp$到前$pos$位数字集合选择状态为$sta$时的方案/总和数。
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=1005;
15 int n,m,k,ban[10];
16 namespace TASK{
17 int a[505],b[505],ad[505],c[5],bin[5][1005],d[1005],e[1005];
18 inline void get(int *a,int x){for(;x;x/=10) a[++a[0]]=x%10;}
19 inline void task1(){
20 a[0]=a[1]=1;
21 for(int T=1;T<=n;T++){
22 memset(ad,0,sizeof(ad));
23 for(int i=1;i<=a[0];i++){
24 int tmp=k*a[i];
25 a[i]=tmp%10; ad[i+1]=tmp/10;
26 if(ad[i]) a[i]+=ad[i];
27 if(a[i]>=10) ad[i+1]+=a[i]/10,a[i]%=10;
28 } if(ad[a[0]+1]) a[0]++,a[a[0]]=ad[a[0]];
29 if(T==n-1) memcpy(b,a,sizeof(a));
30 }
31 for(int i=a[0];i;--i) printf("%lld",a[i]);puts("");
32 if(n==1){cout<<k<<endl;return;}
33 int oo=(1+k)*k/2; get(c,oo);
34 for(int i=1;i<=c[0];i++){
35 memset(ad,0,sizeof(ad));
36 for(int j=1;j<=b[0];j++){
37 int tmp=c[i]*b[j];
38 bin[i][j]=tmp%10; ad[j+1]=tmp/10;
39 if(ad[j]) bin[i][j]+=ad[j];
40 if(bin[i][j]>=10) ad[j+1]+=bin[i][j]/10,bin[i][j]%=10;
41 }
42 bin[i][0]=b[0];
43 while(ad[b[0]+1]){
44 bin[i][++bin[i][0]]=ad[b[0]+1]%10;
45 ad[b[0]+1]/=10;
46 }
47 if(i!=1){
48 bin[i][0]+=(i-1);
49 for(int j=bin[i][0];j>=i-1;j--) bin[i][j]=bin[i][j-i+1];
50 for(int j=1;j<=i-1;j++) bin[i][j]=0;
51 }
52 }
53 int maxn=0; memset(ad,0,sizeof(ad));
54 for(int i=1;i<=c[0];i++) maxn=max(maxn,bin[i][0]);
55 for(int i=1;i<=maxn;i++){
56 int tmp=0;
57 for(int j=1;j<=c[0];j++) tmp+=bin[j][i];
58 ad[i+1]=tmp/10; d[i]=tmp%10;
59 if(ad[i]) d[i]+=ad[i];
60 if(d[i]>=10) ad[i+1]+=d[i]/10,d[i]%=10;
61 } d[0]=maxn;
62 while(ad[maxn+1]){
63 d[++d[0]]=ad[maxn+1]%10;
64 ad[maxn+1]/=10;
65 }
66 memcpy(e,d,sizeof(d));
67 for(int i=1;i<n;i++){
68 memset(ad,0,sizeof(ad));
69 e[0]++;
70 for(int j=e[0];j>1;j--) swap(e[j],e[j-1]);
71 for(int j=1;j<=e[0];j++){
72 int tmp=d[j]+e[j];
73 ad[j+1]=tmp/10,d[j]=tmp%10;
74 if(ad[j]) d[j]+=ad[j];
75 if(d[j]>=10) ad[j+1]+=d[j]/10,d[j]%=10;
76 } if(ad[(d[0]=e[0])+1]) d[0]++,d[d[0]]=ad[d[d[0]]];
77 }
78 for(int i=d[0];i;i--) printf("%lld",d[i]);puts("");
79 }
80 }using namespace TASK;
81 namespace Solve{
82 const int base=1e16;
83 struct Big_Int{
84 int p[65];
85 Big_Int(){}
86 Big_Int(int x){memset(p,0,sizeof(p));p[0]=(x>0);p[1]=x;}
87 inline void print(){
88 printf("%lld",p[p[0]]);
89 for(int i=p[0]-1;i>0;--i) printf("%016lld",p[i]);
90 puts("");
91 }
92 Big_Int operator*(const int&x){
93 Big_Int ret; memset(ret.p,0,sizeof(ret.p)); int add=0; ret.p[0]=p[0];
94 for(int i=1;i<=ret.p[0];++i){
95 ret.p[i]=p[i]*x+add;
96 add=ret.p[i]/base;
97 ret.p[i]-=add*base;
98 }
99 if(add) ret.p[++ret.p[0]]=add;
100 return ret;
101 }
102 Big_Int operator+(const Big_Int&a){
103 Big_Int ret; memset(ret.p,0,sizeof(ret.p)); int add=0; ret.p[0]=max(a.p[0],p[0]);
104 for(int i=1;i<=ret.p[0];++i){
105 ret.p[i]=a.p[i]+p[i]+add;
106 add=ret.p[i]/base;
107 if(ret.p[i]>=base) ret.p[i]-=base;
108 }
109 if(add) ret.p[++ret.p[0]]=add;
110 return ret;
111 }
112 };
113 pair<Big_Int,Big_Int> f[505][1<<9];
114 pair<Big_Int,Big_Int> dfs(int pos,int sta){
115 if(f[pos][sta].first.p[1]>-1) return f[pos][sta];
116 if(pos>n) return f[pos][sta]=make_pair(Big_Int(1),Big_Int(0));
117 f[pos][sta].first.p[1]=0;
118 for(int i=1;i<=k;i++) if(!(sta&(ban[i]))){
119 pair<Big_Int,Big_Int> res=dfs(pos+1,sta|(1<<i-1));
120 f[pos][sta].first=f[pos][sta].first+res.first;
121 f[pos][sta].second=f[pos][sta].second+(res.first*i)+(res.second*10);
122 }
123 return f[pos][sta];
124 }
125 }using namespace Solve;
126 namespace WSN{
127 inline short main(){
128 freopen("hacker2.in","r",stdin);
129 freopen("hacker2.out","w",stdout);
130 n=read();m=read();k=read();
131 if(!m) return task1(),0;
132 for(int i=1,a,b;i<=m;++i) a=read(),b=read(),ban[a]|=1<<b-1;
133 for(int i=1;i<=n+1;i++)
134 for(int j=0;j<(1<<k);j++) f[i][j].first=Big_Int(-1);
135 pair<Big_Int,Big_Int> ans=dfs(1,0);
136 ans.first.print(); ans.second.print();
137 return 0;
138 }
139 }
140 signed main(){return WSN::main();}
View Code