NOIp 2012
day 1 T1 Vigenère 密码
标签：模拟
主要是用了ASCII码，字母'A'的ASCII码是41H（0100 0001B），字母'a'的ASCII码是61H（0110 0001B），字母'A'与'a'的二进制后5位是相同的，所以无论是大写字母还是小写字母x，x &31（1 1111B）的值就是x在字母表里的顺序。
简单判一下边界就行了
code
1 #include <bits/stdc++.h>
2 using namespace std;
3 namespace gengyf{
4 #define ll long long
5 inline int read(){
6 int x=0,f=1;char s=getchar();
7 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
8 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
9 return f*x;
10 }
11 char k[110],s[1010];
12 int main(){
13 cin>>k>>s;
14 int lk=strlen(k),ls=strlen(s);
15 for(int i=0;i<ls;i++){
16 int t=(k[i%lk]&31)-1;
17 s[i]=(s[i]&31)-t>0?s[i]-t:s[i]-t+26;
18 }
19 cout<<s;
20 return 0;
21 }
22 }
23 signed main(){
24 gengyf::main();
25 return 0;
26 }day 1 T2 国王游戏
标签：贪心，高精度
又是一波证明......
king: a0 b0
player1: a1 b1
player2: a2 b2
这种情况下，$ans_1=max(a0/b1，a0*a1/b2)$
king: a0 b0
player2: a2 b2
player1: a1 b1
$ans_2=max(a0/b2，a0*a2/b1)$
显然$a0*a2/b1 > a0/b1$，$a0*a2/b1 > a0/b1$
如果$ans_1$<$ans_2$可知$a0*a2/b1$>$a0*a1/b2$ => $a1*b1<a2*b2$
即$a1*b1<a2*b2$时，$ans_1$<$ans_2$
所以将${a_i}*{b_i}$较小的放在前面更优
code
1 //
2 // main.cpp
3 // Luogu
4 //
5 // Created by gengyf on 2019/7/10.
6 // Copyright © 2019 yifan Geng. All rights reserved.
7 //
8
9 #include <bits/stdc++.h>
10 using namespace std;
11 int sum[20010],now[20010],ans[20010],add[20010];
12 int n;
13 struct Node{
14 int a,b;
15 long long ab;
16 }node[1010];
17 void multi(int x){
18 memset(add,0,sizeof(add));
19 for(int i=1;i<=ans[0];i++){
20 ans[i]*=x;
21 add[i+1]+=ans[i]/10;
22 ans[i]%=10;
23 }
24 for(int i=1;i<=ans[0]+4;i++){
25 ans[i]+=add[i];
26 if(ans[i]>=10){
27 ans[i+1]+=ans[i]/10;
28 ans[i]%=10;
29 }
30 if(ans[i]!=0){
31 ans[0]=max(ans[0],i);
32 }
33 }
34 }
35 int divid(int x){
36 memset(add,0,sizeof(add));
37 int q=0;
38 for(int i=ans[0];i>=1;i--){
39 q*=10;
40 q+=ans[i];
41 add[i]=q/x;
42 if(add[0]==0&&add[i]!=0){
43 add[0]=i;
44 }
45 q%=x;
46 }
47 return 0;
48 }
49 bool compar(){
50 if(sum[0]==add[0]){
51 for(int i=add[0];i>=1;i--){
52 if(add[i]>sum[i]) return 1;
53 if(add[i]<sum[i]) return 0;
54 }
55 }
56 if(add[0]>sum[0]) return 1;
57 if(add[0]<sum[0]) return 0;
58 }
59 void cp(){
60 memset(sum,0,sizeof(sum));
61 for(int i=add[0];i>=0;i--){
62 sum[i]=add[i];
63 }
64 }
65 bool cmp(Node x,Node y){
66 return x.ab<y.ab;
67 }
68 int main(){
69 scanf("%d",&n);
70 for(int i=0;i<=n;i++){
71 scanf("%d%d",&node[i].a,&node[i].b);
72 node[i].ab=node[i].a*node[i].b;
73 }
74 sort(node+1,node+1+n,cmp);
75 ans[0]=1;ans[1]=1;
76 for(int i=1;i<=n;i++){
77 multi(node[i-1].a);
78 divid(node[i].b);
79 if(compar()){
80 cp();
81 }
82 }
83 for(int i=sum[0];i>=1;i--){
84 printf("%d",sum[i]);
85 }
86 return 0;
87 }day 1 T3 开车旅行
标签：倍增，dp，STL，预处理
模拟开车过程，set预处理离城市第一近和第二近的，倍增优化
$g[i][j]=g[g[i][j-1]][j-1]$
$f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0]$
$f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1]$
code(有注释吧)
1 #include <bits/stdc++.h>
2 using namespace std;
3 namespace gengyf{
4 #define ll long long
5 inline int read(){
6 int x=0,f=1;char s=getchar();
7 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
8 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
9 return f*x;
10 }
11 const int maxn=100010;
12 struct node{
13 int num,h;
14 bool operator < (const node a) const{
15 return h<a.h;
16 }
17 }c[maxn];
18 set<node>s;
19 set<node>::iterator it;
20 ll f[maxn][25][2];
21 int nxt[maxn][2],g[maxn][25],dis[maxn][21];
22 int n,x0,m;
23 /*
24 g[i][j]从i开始,两人轮流开2^j轮车后最后到达的位置
25 f[i][j][0]从i开始,两人轮流开2^j轮车后小A走的距离
26 f[i][j][1]从i开始,两人轮流开2^j轮车后小B走的距离
27 nxt[i][0]离i第一近的城市编号
28 nxt[i][1]离i第二近的城市编号
29 dis[i][0]离i第一近的城市到i的距离
30 dis[i][1]离i第二近的城市到i的距离
31 */
32 void update(node x,node y){
33 if(!nxt[x.num][0]){
34 nxt[x.num][0]=y.num;
35 dis[x.num][0]=abs(x.h-y.h);
36 }
37 else if(dis[x.num][0]>abs(x.h-y.h)||(dis[x.num][0]==abs(x.h-y.h)&&y.h<c[nxt[x.num][0]].h)){
38 nxt[x.num][1]=nxt[x.num][0];
39 dis[x.num][1]=dis[x.num][0];
40 nxt[x.num][0]=y.num;
41 dis[x.num][0]=abs(x.h-y.h);
42 }
43 else if(dis[x.num][1]>abs(x.h-y.h)||(dis[x.num][1]==abs(x.h-y.h)&&y.h<c[nxt[x.num][1]].h)){
44 nxt[x.num][1]=y.num;
45 dis[x.num][1]=abs(x.h-y.h);
46 }
47 else if(!nxt[x.num][1]){
48 nxt[x.num][1]=y.num;
49 dis[x.num][1]=abs(x.h-y.h);
50 }
51 return;
52 }
53 void query(int s,int x,ll &disa,ll &disb){
54 for(int i=20;i>=0;i--){
55 if(f[s][i][0]+f[s][i][1]<=x&&g[s][i]){
56 disa+=f[s][i][0];
57 disb+=f[s][i][1];
58 x-=f[s][i][1]+f[s][i][0];
59 s=g[s][i];
60 }
61 }
62 if(nxt[s][1]&&dis[s][1]<=x){
63 disa+=dis[s][1];
64 }
65 }
66 int main(){
67 n=read();
68 for(int i=1;i<=n;i++){
69 c[i].h=read();c[i].num=i;
70 }
71 for(int i=n;i>=1;i--){
72 s.insert(c[i]);
73 it=s.find(c[i]);
74 if(it!=s.begin()){
75 it--;
76 update(c[i],*it);
77 if(it!=s.begin()){
78 it--;
79 update(c[i],*it);
80 it++;
81 }
82 it++;
83 }
84 if((++it)!=s.end()){
85 update(c[i],*it);
86 if((++it)!=s.end()){
87 update(c[i],*it);
88 it--;
89 }
90 it--;
91 }
92 }
93 for(int i=1;i<=n;i++){
94 g[i][0]=nxt[nxt[i][1]][0];
95 f[i][0][0]=dis[i][1];
96 f[i][0][1]=dis[nxt[i][1]][0];
97 }
98 for(int j=1;j<=20;j++)
99 for(int i=1;i<=n;i++){
100 g[i][j]=g[g[i][j-1]][j-1];
101 f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
102 f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
103 }
104 x0=read();ll s0=0,a=1e15,b=0;
105 for(int i=1;i<=n;i++){
106 ll disa=0,disb=0;
107 query(i,x0,disa,disb);
108 if(disb&&(!s0||disa*b<disb*a)){
109 s0=i;a=disa;b=disb;
110 }
111 }
112 printf("%lld\n",s0);
113 m=read();
114 while(m--){
115 ll disa=0,disb=0;
116 int s,x;
117 s=read();x=read();
118 query(s,x,disa,disb);
119 printf("%lld %lld\n",disa,disb);
120 }
121 return 0;
122 }
123 }
124 signed main(){
125 gengyf::main();
126 return 0;
127 }写链表的都是神仙
day 2 T1 同余方程
标签：数论
对于方程$a*x≡1(mod b)$，等价于$a*x+b*y=1$
用exgcd解线性方程，见我之前的博客（不要脸行为
code
1 //
2 // main.cpp
3 // Luogu
4 //
5 // Created by gengyf on 2019/5/7.
6 // Copyright © 2019 yifan Geng. All rights reserved.
7 //
8
9 #include<cstdio>
10 #include<iostream>
11 #include<cstring>
12 #include<string>
13 //#include<bits/stdc++.h>
14 using namespace std;
15 long long a,b,x,y;
16 void exgcd(long xx,long yy){
17 if(yy==0){
18 x=1;y=0;return ;
19 }
20 exgcd(yy,xx%yy);
21 long long tx=x;
22 x=y;
23 y=tx-xx/yy*y;
24 }
25 int main(){
26 scanf("%lld%lld",&a,&b);
27 exgcd(a,b);
28 while(x<0){
29 x+=b;
30 x%=b;
31 }
32 printf("%lld\n",x);
33 }day 2 T2 借教室
标签：二分
利用差分的思想，当一个区间+x时，只需在l处+x，r+1处-x
显然如果一个人不能满足，后面都不能满足，如果可以满足，前面一定都能满足，符合二分性质
code
1 //
2 // main.cpp
3 // Luogu
4 //
5 // Created by gengyf on 2019/7/11.
6 // Copyright © 2019 yifan Geng. All rights reserved.
7 //
8
9 #include <bits/stdc++.h>
10 using namespace std;
11 #define maxn 1000010
12 int d[maxn],s[maxn],t[maxn];
13 int b[maxn],n,m,need[maxn],a[maxn];
14 bool check(int x){
15 memset(b,0,sizeof(b));
16 for(int i=1;i<=x;i++){
17 b[s[i]]+=d[i];
18 b[t[i]+1]-=d[i];
19 }
20 for(int i=1;i<=n;i++){
21 need[i]=need[i-1]+b[i];
22 if(need[i]>a[i])return 0;
23 }
24 return 1;
25 }
26 int main(){
27 scanf("%d%d",&n,&m);
28 for(int i=1;i<=n;i++){
29 scanf("%d",&a[i]);
30 }
31 for(int i=1;i<=m;i++){
32 scanf("%d%d%d",&d[i],&s[i],&t[i]);
33 }
34 int l=1,r=m;
35 if(check(m)){
36 printf("0\n");
37 return 0;
38 }
39 while(l<r){
40 int mid=(l+r)/2;
41 if(check(mid)){
42 l=mid+1;
43 }
44 else r=mid;
45 }
46 printf("-1\n%d",l);
47 return 0;
48 }day 2 T3 疫情控制
标签：倍增，贪心
离根越近，能被叶节点到根的路径经过的越多，所以要在时间允许的范围内尽量把军队向根靠近
上提军队用倍增优化，要求的是最短的移动最多的军队所需时间，二分求解
如果调了很久调不出来，那就重构
code(大概是有注释,如果没有那就是咕了)
1 #include <bits/stdc++.h>
2 using namespace std;
3 namespace gengyf{
4 #define ll long long
5 inline int read(){
6 int x=0,f=1;char s=getchar();
7 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
8 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
9 return f*x;
10 }
11 const int maxn=50010;
12 struct edge{
13 int nxt,to,w;
14 }e[maxn*4];
15 int n,m,q[maxn];
16 int head[maxn],cnt,d[maxn],f[maxn][25],t;
17 bool st[maxn],need[maxn],fl;
18 ll dis[maxn][25],tim[maxn],ned[maxn],ans;
19 pair<ll,int>h[maxn];
20 //q[]输入军队,f[i][j]存i的2^j祖先是谁,dis[i][j]存i到i的2^j祖先的路径长度
21 //d[]深度,st[]驻扎军队,need[]需要驻扎,tim[]军队剩余时间,ned[]仍需驻扎
22 void add(int from,int to,int w){
23 e[++cnt].to=to;e[cnt].nxt=head[from];
24 head[from]=cnt;e[cnt].w=w;
25 }
26 void dfs(){
27 queue<int>q;
28 q.push(1);d[1]=1;
29 while(q.size()){
30 int x=q.front();q.pop();
31 for(int i=head[x];i;i=e[i].nxt){
32 int y=e[i].to;
33 if(d[y])continue;
34 d[y]=d[x]+1;
35 f[y][0]=x;dis[y][0]=e[i].w;
36 for(int j=1;j<=t;j++){//倍增
37 f[y][j]=f[f[y][j-1]][j-1];
38 dis[y][j]=dis[y][j-1]+dis[f[y][j-1]][j-1];
39 }
40 q.push(y);
41 }
42 }
43 }
44 bool dfs2(int x){
45 bool pson=0;//判断是否为叶节点
46 if(st[x])return 1;//是否已经驻扎
47 for(int i=head[x];i;i=e[i].nxt){
48 int y=e[i].to;
49 if(d[x]>d[y])continue;
50 pson=1;//不是叶节点
51 if(!dfs2(y)){
52 return 0;
53 }
54 }
55 if(!pson)return 0;//当前节点是叶子节点且未被驻扎
56 return 1;//没有遇到路径未被驻扎的叶子节点
57 }
58 bool check(ll lim){//lim当前实现
59 memset(st,0,sizeof(st));
60 memset(tim,0,sizeof(tim));
61 memset(need,0,sizeof(need));
62 memset(h,0,sizeof(h));
63 memset(ned,0,sizeof(ned));
64 int atot=0,btot=0,ctot=1;
65 for(int i=1;i<=m;i++){
66 ll x=q[i],tot=0;//tot总共用多少时间
67 for(int j=t;j>=0;j--)
68 if(f[x][j]>1 && tot+dis[x][j]<=lim){//若终点在根节点之前且不会超过时限
69 tot+=dis[x][j];
70 x=f[x][j];
71 }
72 if(f[x][0]==1 && tot+dis[x][0]<=lim)//若当前节点为根节点的子节点且该军队可以在时限内到达根节点
73 h[++ctot]=make_pair(lim-tot-dis[x][0],x);//存储闲置军队
74 else
75 st[x]=1;//标记驻扎
76 }
77 for(int i=head[1];i;i=e[i].nxt){//遍历整棵树
78 if(!dfs2(e[i].to)){//若需要被驻扎
79 need[e[i].to]=1;
80 }
81 }
82 sort(h+1,h+1+ctot);
83 for(int i=1;i<=ctot;i++){//遍历所有闲置的军队
84 if(need[h[i].second] && h[i].first<dis[h[i].second][0])//若该军队所处的节点需要被驻扎且该军队无法到达根节点并返回
85 need[h[i].second]=0;
86 else tim[++atot]=h[i].first;//存储军队的剩余时间
87 }
88 for(int i=head[1];i;i=e[i].nxt){
89 if(need[e[i].to]){//如果仍需要被驻扎
90 ned[++btot]=dis[e[i].to][0];
91 }
92 }
93 if(atot<btot)return 0;//如果剩余的军队比需要被驻扎的节点还少，不可行，直接返回0
94 sort(tim+1,tim+atot+1);
95 sort(ned+1,ned+btot+1);
96 int i=1,j=1;
97 while(i<=btot&&j<=atot){
98 if(tim[j]>=ned[i]){//可行
99 i++;j++;
100 }
101 else j++;
102 }
103 if(i>btot)return 1;//所有需要被驻扎的节点都已被驻扎
104 return 0;
105 }
106 int main(){
107 ll l=0,r=0;
108 n=read();
109 t=log2(n)+1;//倍增
110 for(int i=1;i<n;i++){
111 int u,v,w;
112 u=read();v=read();w=read();
113 add(u,v,w);add(v,u,w);
114 r+=w;
115 }
116 dfs();
117 cin>>m;
118 for(int i=1;i<=m;i++){
119 q[i]=read();
120 }
121 while(l<=r){
122 ll mid=(l+r)>>1;
123 if(check(mid)){
124 r=mid-1;ans=mid;fl=1;//fl有解
125 }
126 else l=mid+1;
127 }
128 if(!fl){
129 printf("-1\n");
130 }
131 else printf("%lld",ans);
132 return 0;
133 }
134 }
135 signed main(){
136 gengyf::main();
137 return 0;
138 }我太难了