pkuwc2018
day0
早上2点到了长沙,感觉被黑车司机坑了。
day1
上午数学还有半个小时选择题还没做完,最后大题只会一题药丸。
下午开场t1写了个暴力提交一直wa,然后调了一个多小时才找出错。
然后发现dt t290分赶紧写t2,然后一直wa,最后发现等于1的情况要特判,然后2个半小时过一题。
然后为了梦想肝t1 nlogn线段树合并,拍了半个小时没过最后发现对拍暴力错的。。
交了一发a了然后看了半个小时榜。
最后100+100+0.
lbc,dt 150,axs 140,jzq60,yk 70好强啊。
day2
半个小时比别人复杂度多个n的暴力直接过了t1。。
感觉状压dp卡常技巧。。
然后一直想t2不会,然后写了个暴力放弃了。
对于2档特殊点也只会n^2暴力(后来发现可以骗数据,学了多项式后发现好蠢啊)
然后最后慢慢地写t3乱搞,不会推期望式子药丸,拿了30。。
最后100+30+30。
yk 150,lbc,axs,jzq 130,dt 120都好强啊。
最后骗了个一本。。
感觉被第二个面试老师套路了。。
wc2018
被垃圾t2错误样例续掉了,然后t1看错题t3没时间写点分树,最后ag滚粗。。
zjoi2018day1
自从pkuwc之后一直在浪。。感觉自己是来送命的。。
考前天天浪到12点,最后一天3人睡大床房。。
然后考试日发现困得不行,而且因为奇怪的外卖拉肚子了。。
意识模糊地写了t1 k=2,k=3,花了半个小时,然后去推新的点等同于原题的什么图。。
然后就被续了1个多小时,偷懒想不打表,考完后发现打表后会容易很多。。
然后写t2,飞快过了大样例尝试写标算过了一个小时发现药丸赶紧去打暴力。。
然后一条链写得意识模糊。
最后写了t1 k=4然后就结束了。
最后30+50+0。。
司机t1爆内存100->50
zyy t1膜人不加分号70->10
%%%wzp 初三第12。

day0
下午到了宾馆,晚上醒来好几次。
day1
到了考场感觉非常渴,然而又没有带杯子。
然而t1开场开始打表,然而考场上的我意识模糊导致打表时ans没清零,又因为是取max导致看了半个小时没看出来。
然后开始推exgcd,过了样列然而一拍就错,感觉自己要爆蛋了。
10点多才拍上,不断优化程序之后竟然发现只有1行,看了一眼时间发现10点半了,感觉自己要回家了。
然而还是在11点前写完了t3,边权等于0的情况会出事,然后一直到12点没过大样列。
出来发现一群人ak了。

晚上又醒来好几次。
day2
看完3题发现都是水题,t2是3^n*n^3,然而卡常卡到0.7s。
t3动态开点线段树。
写完还有1个小时,然后作死卡t3常数把一个数组改成int考完发现爆了。
t2在民间数据奇怪的会wa一个点,而且还是树的情况。

然后测完民间数据估分525,药丸。

出成绩day1 260,day2 250。
day2 t2 for循环应该从0开始枚举,然而我从1开始枚举然后只剩80分
day2 t3 没开longlong,炸成70分。
day2挂成暴力分。
afo快乐。

Lucas定理:C(n,m)=C(n/p,m/p)\*C(n%p,m%p)(以下p均为素数,/为下取整),a=n%p,b=m%p。
证明:有C(p,n)%p=0(n>0&&n<p)。
因为C(p,n)=p!/n!/(n-p)!,p为素数,不可能被消去。
然后有(1+x)^p=1+x^p(%p)。
因为展开后每一项的系数为C(p,i),由C(p,n)%p=0得在%p下均为0。
然后有(1+x)^n=(1+x)^(n/p\*p)\*(1+x)^(n%p)                                         
             =(1+x^p)^(n/p)\*(1+x)^(n%p)(%p下)                                 
             =[x^p\*sum(C(n/p,i))x^i]\*[sum(C(n%p,j))\*x^j](i=1..n/p,j=0..n%p)     
而(1+x)^n=sum(C(n,i)\*(x^i))(i=1..n)                                         
上式左右两边x的某项x^m的系数对p同余,其中左边x^m的系数是C(n,m),因为a,b都小于p,
因此右边的x^m肯定是由x^(m/p\*p)和x^b和(i=m/p,j=b)相乘得到。
如何说明每一项一一对应?考虑到x的值可以任意取,在无数种不同的取值下x^i的值也会改变,而式子始终成立,因此一定一一对应。 

可以将欧拉序转化为括号序列。
访问一个点时加一个左括号,再把这个点放这,离开时放一个右括号。
显然任意两点间的距离即为括号序列中将它们之间可匹配的括号全部去掉后剩下的括号的数量。
可以使用线段树来维护。
以下为将可以匹配括号删除的情况:
c1,c2代表多余的左括号和右括号
l2所有黑点到左端点左括号与右括号的数量的差值的最大值
r2所有黑点到右端点右括号与左括号的数量的差值的最大值
l1所有黑点到左端点的括号数量的最大值
r1所有黑点到右端点的括号数量的最大值
dis代表最大答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<algorithm>
#include<cstdio>
#define ll int
#define inf 1000000000
#define maxn 100010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
char s[10];
ll n,q,cnt,tot,sum;
ll head[maxn],v[maxn*3],next[maxn*2],vet[maxn*2],pos[maxn],c[maxn];
struct data{
ll l1,r1,l2,r2,dis,c1,c2;
void New(ll x){
dis=-inf; c1=c2=0;
if (v[x]==-6) c2=1;
if (v[x]==-9) c1=1;
if (v[x]>0&&c[v[x]]) l1=r1=l2=r2=0;
else l1=r1=l2=r2=-inf;
};
}tr[maxn*12];
data merge(data x,data y){
data s;
ll a=x.c1,b=x.c2,c=y.c1,d=y.c2;
s.dis=max(max(x.dis,y.dis),max(x.r1+y.l2,x.r2+y.l1));
s.r1=max(y.r1,max(x.r1-c+d,x.r2+c+d));
s.l1=max(x.l1,max(y.l1-b+a,y.l2+b+a));
s.r2=max(y.r2,x.r2+c-d);
s.l2=max(x.l2,y.l2+b-a);
if (b<c) s.c1=a-b+c,s.c2=d;
else s.c1=a,s.c2=b-c+d;
return s;
}
void insert(ll x,ll y){
next[++cnt]=head[x]; head[x]=cnt; vet[cnt]=y;
}
void dfs(ll x,ll pre){
v[++tot]=-6; v[++tot]=x; pos[x]=tot;
for(ll i=head[x];i;i=next[i])
if (vet[i]!=pre) dfs(vet[i],x);
v[++tot]=-9;
}
void build(ll p,ll l,ll r){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
void modify(ll p,ll l,ll r,ll x){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
if (x<=mid) modify(p<<1,l,mid,x);
else modify(p<<1|1,mid+1,r,x);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
int main(){
sum=n=read();
For(i,1,n) c[i]=1;
For(i,1,n-1){
ll x=read(),y=read();
insert(x,y); insert(y,x);
}
dfs(1,-1); build(1,1,tot);
q=read();
while(q--){
scanf("%s",s);
if (s[0]=='C'){
ll x=read();
sum-=c[x]?1:-1;
c[x]^=1;
modify(1,1,tot,pos[x]);
}else{
if (!sum) puts("-1");
else if (sum==1) puts("0");
else writeln(tr[1].dis);
}
}
}

这题可以用prufer定理证明。
考虑最后剩下的2个点,一定有连边,那么一定是在不同集合里。
对于其他点,有n种点,总共出现(m-1)次;有m种点,总共出现(n-1)次。
答案为n^(m-1)*m^(n-1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,m,mod;
ll cheng(ll x,ll k){
ll ans=0;
while(k){
if (k&1) (ans+=x)%=mod; (x<<=1)%=mod;
k>>=1;
}
return ans;
}
ll ppow(ll x,ll k){
ll ans=1;
while(k){
if (k&1) ans=cheng(ans,x); x=cheng(x,x);
k>>=1;
}
return ans;
}
int main(){
n=read(); m=read(); mod=read();
writeln(cheng(ppow(n,m-1),ppow(m,n-1)));
}

首先发现可以直接无视0的位置,答案只与有几个1有关,于是优化到了64个状态。
考虑到如果一个状态有偶数个,那么后手可以仿照先手,于是只需要考虑是奇数个的状态。
然后就转化为谁先把所有奇数个全部转化为偶数个,就能胜利。
考虑一个人一次最多减少8个奇数个,最少减少1个,因此转化为另一个,因此只要考虑%9余数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll mark[70],n,ans;
int main(){
n=read();
For(i,1,n){
unsigned ll x=read(),tot=0;
for(;x;x-=x&-x) tot++;
mark[tot]++;
}
For(i,0,65) ans+=mark[i]&1;
if (ans%9) puts("B"); else puts("L");
}

打表后可以发现答案每3个一次循环,因此只需要计算%3的余数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
char s[1010];
ll sum,n;
int main(){
ll T=read();
while(T--){
scanf("%s",s+1);
n=strlen(s+1); sum=0;
For(i,1,n) sum=(sum*10+s[i]-'0')%3;
if (sum) puts("A"); else puts("B");
}
}

nim游戏的sg值为本身,因此只要全部异或就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,ans;
int main(){
n=read();
For(i,1,n) ans^=read();
if (ans) puts("A"); else puts("B");
}

先手和后手每一个来回都可以强制使得取k+1个,因此只需要把总石子数%(k+1),若为0则B必胜,否则A必胜,因为A可以取掉这么多石子使得A和B先取与后取顺序转化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,ans;
int main(){
ll T=read();
while(T--){
ll n=read(),k=read();
if (n%(k+1)) puts("A");
else puts("B");
}
}

可以对sg值打表找规律,可以发现若%7余2或0则B必胜否则A必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
int main(){
ll T=read();
while(T--){
ll t=read()%7;
if (t==2||!t) puts("B"); else puts("A");
}
}