第一题：
给出一个长度不超过100只包含'B'和'R'的字符串，将其无限重复下去。
比如，BBRB则会形成
BBRBBBRBBBRB
现在给出一个区间【l,r】询问该区间内有多少个字符'B'(区间下标从1开始) 【1<=l,r<=1e18】
解： 没想到第一题这么水。直接前缀和+mod就可以了，再判一下边界。注意1e18不需要高精度。long long 有9*10^18.
1 #include
2 #include
3 #include
4 #include
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 。写转移方程的时候遇到了问题，不能表示上一个选的是什么（而从//代码效果参考：http://hnjlyzjd.com/xl/wz_25492.html
这一点出发可以想到换第一维的表示，可以换为last取的食物，于是我与标答失之交臂）所以把 f 写了一个结构体，存下美味值和上一次选的食物。然后就是转移方程，我先循环m，然后枚举所有状态，判断该状态是否符合只取了当前个食物，然后枚举n，加入下一个状态。还是不知道为什么WA了5个点，等写完博客来看看。
50分代码：
1 #include
2 #include
3 #include
4 #include
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
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 }
View Code
说说正解。这道题当初电子科大那位讲过，我说怎么这么眼熟。用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
2 #include
3 #include
4 #include
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
34 f【(1i)】【i+1】=v【i+1】;
35 int idx=1;
36 for (int i=1;i<=(1n);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
