[codeforces 1337F] Yui and Mahjong Set 公式推导+交互式程序的测试
Codeforces Round #635 (Div. 2) 比赛人数14830
[codeforces 1337F] Yui and Mahjong Set 公式推导+交互式程序的测试
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.com/contest/1337/problem/F
| Problem | Lang | Verdict | Time | Memory |
|---|---|---|---|---|
| D - Yui and Mahjong Set | GNU C++17 | Accepted | 31 ms | 0 KB |
说明：下面呈现的内容，比较繁重，若要看懂，希望读者能拿出纸笔，进行跟随。
做到这个份上的题目，不是轻易就能弄明白的。
样例理解如下
Input:
5
1 6
2 9
5 12
5 24
6 24
Output:
+ 1
+ 1
+ 2
+ 5
! 2 1 3 0 2
样例模拟如下
1 6
可以猜测1*2*3=6
+ 1
2 9
可以猜测1*(2+1)*3=9 现可确定初始数组1的个数是2,
可以推测straight是(1,2,3),定初始数组4的个数是0
+ 1
5 12
1*(2+1+1)*3=12 C(4,3)+C(3,3)=5,此次交互对猜测结果无任何贡献，属无效交互
+ 2
5 24
(1+1)*(2+1+1)*3=24,现可确定初始数组2的个数是1,可确定初始数组3的个数是3
+ 5
6 24
C(4,3)+C(3,3)+C(3,3)=6,现可确定初始数组5的个数是2
样例是弄明白了，但感觉上述过程，毫无章法可言。
突然想到,既然投机取巧不成,还不如死板些,按1,2,3,......,n的顺序方式插入数值,看看对triplet数量的影响,对straight数量的影响
ans[i]代表值为i的数量
可先精确算出ans[1],ans[2],ans[3]
之后利用递推关系，算出ans[4],ans[5],......,ans[n-1]
最后再利用公式算出ans[n];
该题关键技巧是。两次插入1,精确算出ans[1]
1.1若加入数值i，triplet数量有变动，那就太好了，初始数组中i的数量n就确定了，计算如下
C(n+1,3)-C(n,3)=triplet数量的变动
(n+1)*n*(n-1)/(3*2)-n*(n-1)*(n-2)/(3*2)=n(n-1)/2
即n(n-1)/2=triplet数量的变动,这个时候，就没有straight数量变动的事了。
谈一下ans[1]=m,m的求法
以下针对triplet数量
0什么都不加
C(m,3)+其他
1第一次加入1
C(m+1,3)+其他
0->1对应的变化量
C(m+1,3)-C(m,3)
(n-1)第一次加入(n-1)
C(m+1,3)+其他量
n第二次加入1
C(m+2,3)+其他量
n-1->n对应的变化量
C(m+2,3)-C(m+1,3)
(n-1)->n对应的变化量 与 0->1对应的变化量 的差值
(C(m+2,3)-C(m+1,3))-(C(m+1,3)-C(m,3))
=C(m+2,3)+C(m,3)-2*C(m+1,3)
=(m+2)*(m+1)*m/6+m*(m-1)*(m-2)/6-2(m+1)*m*(m-1)/6
=m
可见ans[1]精确可求。
1.1若加入数值i，triplet数量无变动，那么可以推断，初始数组中i的数量是0或1
2.此时，就需要查看straight数量的变动了，
因straight数量变动,研究起来，比较复杂，故考虑，记录交互过程，之后离线处理。
两遍处理，第一遍，处理triplet数量变动，精确算出，引起triplet数量变动的i的初始数量
若加入的i值引起triplet数量变动，那么i的初始数量，精确可求。
注意，若加入的i值未引起triplet数量变动，那么i的数量只有两种情况0或者1
第二遍，处理straight数量的变动,算出剩下的i值的数量
以7个数为例，讨论straight数量
0什么都不加
ans[1]*ans[2]*ans[3]+ans[2]*ans[3]*ans[4]+ans[3]*ans[4]*ans[5]+
ans[4]*ans[5]*ans[6]+ans[5]*ans[6]*ans[7]
1加入数值1
(ans[1]+1)*ans[2]*ans[3]+ans[2]*ans[3]*ans[4]+ans[3]*ans[4]*ans[5]+
ans[4]*ans[5]*ans[6]+ans[5]*ans[6]*ans[7]
0->1对应的变化量
ans[2]*ans[3]
2加入数值2
(ans[1]+1)*(ans[2]+1)*ans[3]+(ans[2]+1)*ans[3]*ans[4]+ans[3]*ans[4]*ans[5]+
ans[4]*ans[5]*ans[6]+ans[5]*ans[6]*ans[7]
1->2对应的变化量
(ans[1]+1)*ans[3]+ans[3]*ans[4] 可求a[3]
3加入数值3
(ans[1]+1)*(ans[2]+1)*(ans[3]+1)+(ans[2]+1)*(ans[3]+1)*ans[4]+
(ans[3]+1)*ans[4]*ans[5]+ans[4]*ans[5]*ans[6]+ans[5]*ans[6]*ans[7]
2->3对应的变化量
(ans[1]+1)*(ans[2]+1)+(ans[2]+1)*ans[4]+ans[4]*ans[5]
4加入数值4
(ans[1]+1)*(ans[2]+1)*(ans[3]+1)+(ans[2]+1)*(ans[3]+1)*(ans[4]+1)+
(ans[3]+1)*(ans[4]+1)*ans[5]+(ans[4]+1)*ans[5]*ans[6]+ans[5]*ans[6]*ans[7]
3->4对应的变化量
(ans[2]+1)*(ans[3]+1)+(ans[3]+1)*ans[5]+ans[5]*ans[6]
5加入数值5
(ans[1]+1)*(ans[2]+1)*(ans[3]+1)+(ans[2]+1)*(ans[3]+1)*(ans[4]+1)+
(ans[3]+1)*(ans[4]+1)*(ans[5]+1)+(ans[4]+1)*(ans[5]+1)*ans[6]+
(ans[5]+1)*ans[6]*ans[7]
4->5对应的变化量
(ans[3]+1)*(ans[4]+1)+(ans[4]+1)*ans[6]+ans[6]*ans[7]
6加入数值6
(ans[1]+1)*(ans[2]+1)*(ans[3]+1)+(ans[2]+1)*(ans[3]+1)*(ans[4]+1)+
(ans[3]+1)*(ans[4]+1)*(ans[5]+1)+(ans[4]+1)*(ans[5]+1)*(ans[6]+1)+
(ans[5]+1)*(ans[6]+1)*ans[7]
5->6对应的变化量
(ans[4]+1)*(ans[5]+1)+(ans[5]+1)*ans[7] 可求a[7]
7加入数值1
(ans[1]+1+1)*(ans[2]+1)*(ans[3]+1)+(ans[2]+1)*(ans[3]+1)*(ans[4]+1)+
(ans[3]+1)*(ans[4]+1)*(ans[5]+1)+(ans[4]+1)*(ans[5]+1)*(ans[6]+1)+
(ans[5]+1)*(ans[6]+1)*(ans[7]+1)
6->7对应的变化量
(ans[2]+1)*(ans[3]+1) 可求a[2]有一个疑问，交互式程序，在本机上，如何测试，或者说调试吧。
代码调试过程，上述问题，就解决了。
需要按编程者自己的算法，构造出相应的数据，即可调试
将样例改造成，对应之后AC代码的测试数据如下
Input:
5
1 6
2 9
2 18
5 24
5 40
8 48
Output:
+ 1
+ 2
+ 3
+ 4
+ 1
! 2 1 3 0 2
上述测试数据，获得的过程如下
5
1 6 (1,1,2,3,3,3,5,5) C(3,3)=1 2*1*3=6
2 9 (1,1,1,2,3,3,3,5,5) C(3,3)+C(3,3)=2 3*1*3=9
2 18 (1,1,1,2,2,3,3,3,5,5) C(3,3)+C(3,3)=2 3*2*3=18
5 24 (1,1,1,2,2,3,3,3,3,5,5) C(3,3)+C(4,3)=5 3*2*4=24
5 40 (1,1,1,2,2,3,3,3,3,4,5,5) C(3,3)+C(4,3)=5 3*2*4+2*4*1+4*1*2=40
8 48 (1,1,1,1,2,2,3,3,3,3,4,5,5) C(4,3)+C(4,3)=8 4*2*4+2*4*1+4*1*2=48AC代码如下
#include <stdio.h>
#define maxn 105
int n,ans[maxn],cnt;
struct node{
int x,y;
}a[maxn];
void ask(int k){//交互
printf("+ %d\n",k);
fflush(stdout);
cnt++;
scanf("%d%d",&a[cnt].x,&a[cnt].y);//交互式时,要小心,不能将cnt合并进来,写成scanf("%d%d",&a[++cnt].x,&a[cnt].y);
}
int main(){
int i;
scanf("%d",&n);
scanf("%d%d",&a[0].x,&a[0].y);
for(i=1;i<=n;i++)ans[i]=-1;//初始化
for(i=1;i<=n-1;i++)ask(i);
ask(1);//为了精确求ans[1],而询问
for(i=n;i>=1;i--)a[i].x-=a[i-1].x,a[i].y-=a[i-1].y;//求triplet,straight变化量
ans[1]=a[n].x-a[1].x;
for(i=2;i<=n-1;i++)
if(a[i].x){//根据triplet进行精确求解
ans[i]=0;
while(ans[i]*(ans[i]-1)/2<a[i].x)ans[i]++;
}
if(ans[3]==-1)ans[3]=(a[2].y>0);//ans[3]精确可求
if(ans[2]==-1)ans[2]=a[n].y/(ans[3]+1)-1;//ans[2]精确可求
for(i=3;i<=n-2;i++)
if(ans[i+1]==-1){//可求4,5,6,......,n-1
a[i].y-=(ans[i-1]+1)*(ans[i-2]+1);
ans[i+1]=(a[i].y>0);
}
ans[n]=(a[n-1].y-(ans[n-2]+1)*(ans[n-3]+1))/(ans[n-2]+1);//求ans[n];
printf("!");
for(i=1;i<n;i++)printf(" %d",ans[i]);
printf(" %d\n",ans[n]);
return 0;
}通过该题，第一次见识了交互式程序，总体来说，造数据是比较耗时的。