文章发表于比赛之后。。。
（之前是没有选发表，仅本人可见，然后比赛后再按了发表，而博客时间以第一次创建的时间计算）
update:
不满足打满全场的情况
判断前1个赛季（第2个赛季开始，值为负数；它的值比第1个赛季开始的时候更小）
满足打满全场的情况
最后部分场次可以不打
所以都要考虑一个赛季的情况
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e2+10; 15 16 char str[maxn]; 17 18 int main() 19 { 20 ll n,m,K,g,t,i,j,r,win; 21 scanf("%lld",&t); 22 while (t--) 23 { 24 scanf("%lld%lld%lld%s",&n,&K,&m,str+1); 25 26 win=0,j=K,r=0,g=0; 27 for (i=1;i<=n;i++) 28 { 29 if (str[i]=='1') 30 win++,g++; 31 else if (j>0) 32 j--; 33 else 34 win--; 35 r=max(r,win); 36 } 37 38 printf("%lld ",max(0ll,g-max((n-g)-K,0ll))*(m-1) + r); 39 } 40 return 0; 41 } 42 /** 43 100 44 5 2 5 45 11000 46 47 7 2 5 48 1100000 49 50 7 2 5 51 0000011 52 **/
old:
判断前2个赛季（第2个赛季开始，值为负数；若还有第3个赛季，它的值比第2个赛季开始的时候更小）
满足打满全场的情况
最后部分场次可以不打
所以都要考虑两个赛季的情况
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=3e2+10; 15 16 ll a[maxn]; 17 18 int main() 19 { 20 ll n,m,k,g,t,i,j,r,x,y,z,win; 21 char c; 22 scanf("%lld",&t); 23 while (t--) 24 { 25 scanf("%lld%lld%lld ",&n,&k,&m); 26 g=0; 27 for (i=1;i<=n;i++) 28 { 29 scanf("%c",&c); 30 if (c=='1') 31 { 32 g++; 33 a[i]=1; 34 } 35 else 36 a[i]=0; 37 } 38 for (i=n+1;i<=n*2;i++) 39 a[i]=a[i-n]; 40 for (i=2*n+1;i<=n*3;i++) 41 a[i]=a[i-n*2]; 42 if (g==0) 43 printf("0 "); 44 else 45 { 46 win=0,j=0,r=0; 47 for (i=1;i<=min(2ll,m)*n;i++) 48 { 49 if (i%n==1) 50 j+=k; 51 52 if (a[i]) 53 win++; 54 else if (j>0) 55 j--; 56 else 57 win--; 58 r=max(r,win); 59 } 60 if (m<=2 || g<(n-g)-k) 61 printf("%lld ",r); 62 else 63 printf("%lld ",(m-2)*( g - max((n-g)-k,0ll) ) + r); 64 65 } 66 } 67 return 0; 68 } 69 /** 70 100 71 5 2 5 72 11000 73 74 7 2 5 75 1100000 76 77 7 2 5 78 0000011 79 **/
判断环
dfs 记录路径&是否访问过
环：position x~position y
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e5+10; 15 16 struct node 17 { 18 int d,len; 19 node *to; 20 }*e[maxn],*findlen[maxn]; 21 22 int a[maxn],b[maxn],ind[maxn],v[maxn],root,fa[maxn]; 23 bool ifok,vis[maxn]; 24 25 void dfs(int d,int index) 26 { 27 if (ifok) 28 return; 29 vis[d]=1; 30 b[index]=d; 31 ind[d]=index; 32 node *p=e[d]; 33 while (p) 34 { 35 if (ifok) 36 return; 37 findlen[index]=p; 38 if (!vis[p->d]) 39 { 40 fa[p->d]=d; 41 dfs(p->d,index+1); 42 } 43 else if (p->d!=fa[d]) 44 { 45 int i,j=ind[p->d]; 46 ll tot=0,tot1=0; 47 for (i=j;i<=index;i++) 48 { 49 p=findlen[i]; 50 tot+=p->len; 51 if ((i-j)%2==1) 52 tot1+=p->len; 53 } 54 55 root=p->d; 56 v[p->d]=tot/2-tot1; 57 ifok=1; 58 return; 59 } 60 p=p->to; 61 } 62 } 63 64 void work(int d) 65 { 66 vis[d]=1; 67 node *p=e[d]; 68 while (p) 69 { 70 if (!vis[p->d]) 71 { 72 v[p->d]=p->len-v[d]; 73 work(p->d); 74 } 75 p=p->to; 76 } 77 } 78 79 int main() 80 { 81 node *p; 82 int n,i,x,y,z; 83 scanf("%d",&n); 84 for (i=1;i<=n;i++) 85 { 86 scanf("%d%d%d",&x,&y,&z); 87 p=new node(); 88 p->d=y; 89 p->len=z; 90 p->to=e[x]; 91 e[x]=p; 92 93 p=new node(); 94 p->d=x; 95 p->len=z; 96 p->to=e[y]; 97 e[y]=p; 98 } 99 dfs(1,1); 100 101 memset(vis,0,sizeof(vis)); 102 work(root); 103 104 for (i=1;i<=n;i++) 105 printf("%d ",v[i]); 106 return 0; 107 } 108 /* 109 5 110 1 2 2 111 2 3 2 112 3 4 2 113 4 5 2 114 5 1 2 115 116 6 117 1 2 1 118 2 3 3 119 3 4 4 120 4 2 5 121 5 3 100 122 6 4 2 123 */
对于x-1,x扇形：
分成1~x-2,x+1~n两部分
对于下一个扇形x,x+1
分成
1-~x-2 到它
x+1到它
x+2~n到它
而x+1~n这部分，对于任意的数字，它们的情况都是一样的（在这之前，没有约束）
所以x的情况为总情况除以相应的个数
这个代码里面有求1~n的逆元，即i^-1
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=5e5+10; 15 16 ll ch[maxn],fan_ch[maxn],rev[maxn]; 17 18 ll mul(ll a,ll b) 19 { 20 ll y=1; 21 while (b) 22 { 23 if (b&1) 24 y=y*a%mod; 25 a=a*a%mod; 26 b>>=1; 27 } 28 return y; 29 } 30 31 int maxv=5e5; 32 33 int main() 34 { 35 int t; 36 ll n,m,i,a,b,aa,bb,c,d,x; 37 ch[1]=1; 38 for (i=2;i<=maxv;i++) 39 ch[i]=ch[i-1]*i%mod; 40 fan_ch[maxv]=mul(ch[maxv],mod-2); 41 for (i=maxv;i>=1;i--) 42 { 43 fan_ch[i-1]=fan_ch[i]*i%mod; 44 rev[i]=fan_ch[i]*ch[i-1]%mod; 45 } 46 rev[1]=1; 47 48 scanf("%d",&t); 49 while (t--) 50 { 51 scanf("%lld%lld",&n,&m); 52 53 ///x=1 54 a=0; 55 b=m-3+1; 56 for (x=2;x<n;x++) 57 { 58 c=b*rev[m-(x+1)+1]%mod; 59 d=c*(m-(x+1)+1-1)%mod; 60 aa=(a*(x-1-1) + c*(x-1) + d*(x-1))%mod; 61 bb=(a*(m-(x+2)+1) + c*(m-(x+2)+1) + d*(m-(x+2)+1-1))%mod; 62 63 a=aa; 64 b=bb; 65 } 66 67 ///P(m,n) 68 printf("%lld ",(a+b)%mod*ch[m]%mod*fan_ch[m-n]%mod); 69 } 70 return 0; 71 }
update:
对于x-1,x扇形：
分成1~x-2,x+1~n两部分
每个x+1~n，每个数的情况数目都是一样的，
而对于1~x-2，每个数的情况数目 不 都是一样的，
如处理到x,x+1扇形时，
1~x-2和x-1的情况不同，
因为1~x-2拓展到1~x-2 和 1~x-2拓展到x-1 的方案数不同。