文章发表于比赛之后。。。
（之前是没有选发表，仅本人可见，然后比赛后再按了发表，而博客时间以第一次创建的时间计算）
update:
不满足打满全场的情况
判断前1个赛季（第2个赛季开始，值为负数；它的值比第1个赛季开始的时候更小）
满足打满全场的情况
最后部分场次可以不打
所以都要考虑一个赛季的情况
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 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 else34 win--;35 r=max(r,win);36 }37 38 printf("%lld\n",max(0ll,g-max((n-g)-K,0ll))*(m-1) + r);39 }40 return 0;41 }42 /**43 10044 5 2 545 1100046 47 7 2 548 110000049 50 7 2 551 000001152 **/
old:
判断前2个赛季（第2个赛季开始，值为负数；若还有第3个赛季，它的值比第2个赛季开始的时候更小）
满足打满全场的情况
最后部分场次可以不打
所以都要考虑两个赛季的情况
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 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",&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 else36 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\n");44 else45 {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 else57 win--;58 r=max(r,win);59 }60 if (m<=2 || g<(n-g)-k)61 printf("%lld\n",r);62 else63 printf("%lld\n",(m-2)*( g - max((n-g)-k,0ll) ) + r);64 65 }66 }67 return 0;68 }69 /**70 10071 5 2 572 1100073 74 7 2 575 110000076 77 7 2 578 000001179 **/
判断环
dfs 记录路径&是否访问过
环：position x~position y
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 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\n",v[i]);106 return 0;107 }108 /*109 5110 1 2 2111 2 3 2112 3 4 2113 4 5 2114 5 1 2115 116 6117 1 2 1118 2 3 3119 3 4 4120 4 2 5121 5 3 100122 6 4 2123 */
对于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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 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=154 a=0;55 b=m-3+1;56 for (x=2;x
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 的方案数不同。