第一题：
给出一个长度不超过100只包含'B'和'R'的字符串，将其无限重复下去。
比如，BBRB则会形成
BBRBBBRBBBRB
现在给出一个区间[l,r]询问该区间内有多少个字符'B'(区间下标从1开始) [1<=l,r<=1e18]
解： 没想到第一题这么水。直接前缀和+mod就可以了，再判一下边界。注意1e18不需要高精度。long long 有9*10^18.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 105 6 #define ll long long 7 using namespace std; 8 char c[maxn]; 9 ll len,ans,l,r,sum[maxn]; 10 int main() 11 { 12 freopen("a.in","r",stdin); 13 freopen("a.out","w",stdout); 14 scanf("%s",c+1); 15 cin>>l>>r; 16 len=strlen(c+1); 17 for (int i=1;i<=len;i++) 18 { 19 sum[i]=sum[i-1]; 20 if (c[i]=='B') sum[i]++; 21 } 22 ans=(r/len)*sum[len]+sum[r%len]-(l/len)*sum[len]-sum[l%len]; 23 if ((l%len==0&&c[len]=='B')||c[l%len]=='B') ans++; 24 printf("%I64d",ans); 25 return 0; 26 }
第二题：（codeforces 580D:Kefa and Dishes）
我们要从n种食物选m个出来，安排一个顺序吃掉它（们），每种食物有个美味值ai，然后我们有k个规则，每个规则有 xi, yi 和 ci三个数，如果吃完第xi种食物接下来马上吃第yi种食物，第j种食物的美味值会增加ci。每种食物至多吃一个，求美味值最大的和是多少？
n,m<=18,ai,ci<=10^9
解：
看到这么小的数据范围就是状压dp了。想到是第一次自己写，还是很欣慰的得了50%。我的方法是f[i][j]表示选了 i 个的状态 j 。写转移方程的时候遇到了问题，不能表示上一个选的是什么（而从这一点出发可以想到换第一维的表示，可以换为last取的食物，于是我与标答失之交臂）所以把 f 写了一个结构体，存下美味值和上一次选的食物。然后就是转移方程，我先循环m，然后枚举所有状态，判断该状态是否符合只取了当前个食物，然后枚举n，加入下一个状态。
还是不知道为什么WA了5个点，等写完博客来看看。
50分代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M 300000 6 #define maxn 20 7 #define ll long long 8 using namespace std; 9 int n,m,k,ma; 10 ll v[maxn]; 11 struct pp{ 12 ll tastyy; 13 int chos; 14 }; 15 pp f[maxn][M]; 16 ll ad[maxn][maxn]; 17 bool pd(int x,int y) 18 { 19 int sum=0; 20 for (int i=0;i<n;i++) 21 { 22 if ((1<<i)&x) sum++; 23 if (sum>y-1) return false; 24 } 25 if (sum==y-1) return true; 26 else return false; 27 } 28 int main() 29 { 30 freopen("b.in","r",stdin); 31 freopen("b.out","w",stdout); 32 scanf("%d%d%d",&n,&m,&k); 33 for (int i=1;i<=n;i++) 34 scanf("%I64d",&v[i]); 35 for (int i=1;i<=k;i++) 36 { 37 int x,y; 38 ll z; 39 scanf("%d%d%I64d",&x,&y,&z); 40 ad[x][y]=z; 41 } 42 for (int i=1;i<=m;i++) 43 { 44 f[i][0].tastyy=-1; 45 ma=(ma|(1<<(n-i)));//n-i 46 } 47 for (int i=1;i<=n;i++) 48 { 49 int x=(1<<(i-1));// not f[1][i] 50 f[1][x].tastyy=v[i]; 51 f[1][x].chos=i; 52 } 53 for (int i=2;i<=m;i++) 54 { 55 for (int j=1;j<=ma;j++) 56 if (pd(j,i)&&f[i-1][j].tastyy){ 57 for (int k=1;k<=n;k++) 58 if (f[i][(j&(1<<(k-1)))].tastyy==-1){ 59 int cur=(j|(1<<(k-1)));//k-1 60 ll add=0; 61 if (ad[f[i-1][j].chos][k]) add=ad[f[i-1][j].chos][k]; 62 if (f[i-1][j].tastyy+v[k]+add>=f[i][cur].tastyy){//放在括号内 63 f[i][cur].tastyy=f[i-1][j].tastyy+v[k]+add; 64 f[i][cur].chos=k; 65 } 66 } 67 } 68 } 69 ll ans=0; 70 for (int i=1;i<=ma;i++) 71 if (f[m][i].tastyy>=0){ 72 if (f[m][i].tastyy>=ans) ans=f[m][i].tastyy; 73 } 74 printf("%I64d",ans); 75 return 0; 76 }
说说正解。这道题当初电子科大那位讲过，我说怎么这么眼熟。用f[i][j]表示最后一个选 j 的状态 i 。第一层枚举所有状态，进入后判断是否选了m个更新答案，否则，第二层循环当前要选的点，如果当前状态没有选过，那么进入第三层，循环上一次能选的点，更新状态：f[(i|(1<<(j-1)))][j]=max(f[(i|(1<<(j-1)))][j],f[i][k]+ad[k][j]+v[j]) 。
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M 300000 6 #define maxn 20 7 #define ll long long 8 using namespace std; 9 int n,m,k; 10 ll v[maxn],f[M][maxn],ad[maxn][maxn],ans; 11 bool pd(int x) 12 { 13 int sum=0;//sum=0 14 for (int i=1;i<=n;i++) 15 if ((1<<(i-1))&x) sum++;//&x 16 if (sum==m) return true; 17 else return false; 18 } 19 int main() 20 { 21 freopen("b.in","r",stdin); 22 freopen("b.out","w",stdout); 23 cin>>n>>m>>k; 24 for (int i=1;i<=n;i++) 25 scanf("%I64d",&v[i]); 26 for (int i=1;i<=k;i++) 27 { 28 int x,y; 29 ll z; 30 scanf("%d%d%I64d",&x,&y,&z); 31 ad[x][y]=z; 32 } 33 for (int i=0;i<n;i++) 34 f[(1<<i)][i+1]=v[i+1]; 35 int idx=1; 36 for (int i=1;i<=(1<<n);i++) 37 { 38 if (pd(i)){ 39 for (int j=1;j<=n;j++) 40 if (f[i][j]>ans) ans=f[i][j]; 41 } 42 else{ 43 for (int j=1;j<=n;j++) 44 { 45 if (((i>>(j-1))&1)==0) 46 {//没有吃 47 for (int k=1;k<=n;k++) 48 if ((i>>(k-1))&1)//枚举吃过的最后一个 49 { 50 if (f[i][k]+ad[k][j]+v[j]>f[(i|(1<<(j-1)))][j]) 51 f[(i|(1<<(j-1)))][j]=f[i][k]+ad[k][j]+v[j]; 52 } 53 } 54 } 55 } 56 } 57 printf("%I64d",ans); 58 return 0; 59 }
第三题：
因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为0。当城市i被加派了k名士兵时。城市?的所有子城市需要被加派k + 1名士兵。这些子城市的所有子城市需要被加派k +2名士兵。以此类推。当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能询问以城市 i 为根的子树中的所有城市共被加派了多少士兵。你现在是国王的军事大臣，你能回答出国王的每个询问么？
输入格式
第一行，包含两个整数N,P代表城市数量以及国王的命令的数量。
第二行N −1个整数，表示2− N号每个节点的父亲节点。
接下来的P行，每行代表国王的一个命令，命令分两种:
A X K在城市X加入K个士兵
Q X 询问以城市X为根的子树中所有士兵数量的和。
n<=50000,p<=100000
解： 考试时用20多分钟打的暴力，过了50%。然后这套题就考了200。这是集训以来考的最好的一次，第4吧。
说正事。这道题的正解：dfs序+线段树。
dfs序：按照dfs的搜索顺序，一个节点的所有子树都是连续的标号，所以对于这个节点有一个最大区间，可以用线段树进行维护。（QAQ树套树-_-）
最终还是逃不过线段树。每一次操作u节点对于u的某一子树上的节点v而言，需要加上的值为k+dep[v]-dp[u]. dep[v]为节点本身的性质，而k-dep[u]为子树的性质。所以可以把它分为两部分处理。一个节点如果被操作了tot次，那么第一部分为tot*dep[v] , 对于子树而言，为tot*∑dep[v]。同样第二部分，每个子节点都是k-dep[u]，所以对于这棵子树为size*(k-dep[u]).
然后就是线段树的长长代码.....还要多练啊。提速。注意一些细节，毕竟代码长了容易犯小错误，而且这样的小错是很难找到的。我运气还算比较好。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 50005 6 #define ll long long 7 #define L(x) (x<<1) 8 #define R(x) ((x<<1)|1) 9 #ifdef WIN32 10 #define AUTO "%I64d" 11 #else 12 #define AUTO "%lld" 13 #endif 14 using namespace std; 15 int n,q,ans,idx; 16 int tot,ne[maxn*2],to[maxn*2],he[maxn],id[maxn]; 17 int xul[maxn],xur[maxn],depth[maxn]; 18 19 void add(int a,int b) 20 { 21 tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot; 22 } 23 void dfs_xu(int x,int fa,int dep) 24 { 25 depth[x]=dep; 26 xul[x]=++idx;//正序左 27 id[idx]=x;//反之 28 for (int i=he[x];i;i=ne[i]) 29 if (to[i]!=fa){ 30 dfs_xu(to[i],x,dep+1); 31 } 32 xur[x]=idx;//右端点 33 } 34 /* /*-----------------xian_duan_shu-----------------------*/ 35 struct pp{ 36 ll dep,sum_tot,tot;//sum_tot: part_1 37 ll cha,sum_cha,size;//sum_cha作为子树的sum，cha 作为单点的cha, 38 }; 39 pp tree[maxn*4]; 40 /*-------------add_dan----------------*/ 41 void add_tot(int x,ll val) 42 { 43 tree[x].tot+=val; 44 tree[x].sum_tot+=val*tree[x].dep; 45 } 46 void add_cha(int x,ll val) 47 { 48 tree[x].cha+=val; 49 tree[x].sum_cha+=val*tree[x].size; 50 } 51 /*-------------------pushdown--------------------*/ 52 void pushdown_tot(int cur) 53 { 54 if (!tree[cur].tot) return ; 55 add_tot(L(cur),tree[cur].tot); 56 add_tot(R(cur),tree[cur].tot); 57 tree[cur].tot=0; 58 } 59 void pushdown_cha(int cur) 60 { 61 if(!tree[cur].cha) return ; 62 add_cha(L(cur),tree[cur].cha); 63 add_cha(R(cur),tree[cur].cha); 64 tree[cur].cha=0; 65 } 66 /*----------------------uptate_sum---------------------*/ 67 void uptate_tot(int cur) 68 { 69 tree[cur].sum_tot=tree[L(cur)].sum_tot+tree[R(cur)].sum_tot; 70 } 71 void uptate_cha(int cur) 72 { 73 tree[cur].sum_cha=tree[L(cur)].sum_cha+tree[R(cur)].sum_cha; 74 } 75 /*-----------------------------opreate-------------------------------*/ 76 void change_tot(int cur,int l,int r,int x,int y,ll val) 77 { 78 if (l>=x&&r<=y) 79 { 80 add_tot(cur,val); 81 return ; 82 } 83 pushdown_tot(cur); 84 int mid=(l+r)>>1; 85 if (x<=mid&&l<=y) change_tot(L(cur),l,mid,x,y,val); 86 if (y>=mid+1&&x<=r) change_tot(R(cur),mid+1,r,x,y,val); 87 uptate_tot(cur); 88 } 89 void change_cha(int cur,int l,int r,int x,int y,ll val) 90 { 91 if (l>=x&&r<=y) 92 { 93 add_cha(cur,val); 94 return ; 95 } 96 pushdown_cha(cur); 97 int mid=(l+r)>>1; 98 if (x<=mid&&l<=y) change_cha(L(cur),l,mid,x,y,val); 99 if (y>=mid+1&&x<=r) change_cha(R(cur),mid+1,r,x,y,val); 100 uptate_cha(cur); 101 } 102 ll query(int cur,int l,int r,int x,int y) 103 { 104 if (x<=l&&r<=y) 105 return tree[cur].sum_tot+tree[cur].sum_cha; 106 pushdown_tot(cur);pushdown_cha(cur); 107 int mid=(l+r)>>1; 108 ll an=0; 109 if (x<=mid&&l<=y) an+=query(L(cur),l,mid,x,y); 110 if (y>=mid+1&&x<=r) an+=query(R(cur),mid+1,r,x,y); 111 return an; 112 } 113 /*----------------------build-----------------------*/ 114 115 void update_build(int u) 116 { 117 tree[u].size=tree[L(u)].size+tree[R(u)].size; 118 tree[u].dep=tree[L(u)].dep+tree[R(u)].dep;//细节 119 } 120 void build(int l,int r,int u) 121 { 122 if (l==r) 123 { 124 tree[u].dep=depth[id[l]]; 125 tree[u].size=1; 126 return ;//**** 127 } 128 int mid=(l+r)>>1; 129 build(l,mid,L(u)); 130 build(mid+1,r,R(u));//mid+1 131 update_build(u); 132 } 133 /*-------------------------main----------------------------*/ 134 int main() 135 { 136 freopen("c.in","r",stdin); 137 freopen("c.out","w",stdout); 138 cin>>n>>q; 139 for (int i=2;i<=n;i++) 140 { 141 int x; 142 scanf("%d",&x); 143 add(x,i); 144 add(i,x); 145 } 146 dfs_xu(1,0,1); 147 build(1,n,1); 148 while (q) 149 { 150 char c[2];int x; 151 scanf("%s",c); 152 if (c[0]=='A') { 153 int x; 154 ll y; 155 scanf("%d"AUTO,&x,&y); 156 change_tot(1,1,n,xul[x],xur[x],1); 157 change_cha(1,1,n,xul[x],xur[x],y-depth[x]); 158 } 159 else { 160 int x; 161 scanf("%d",&x); 162 ll ans=query(1,1,n,xul[x],xur[x]); 163 printf(AUTO,ans); 164 printf(" "); 165 } 166 q--; 167 } 168 return 0; 169 }