正文
纪中2018暑假培训day3提高a组改题记录（混有部分b组）
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
day3
模拟赛，看了看a组题，发现是博弈论，非常开心（因为好玩），于是做的a组。结果差点爆零，死命纠结t1的sg函数，但其实只是一个dp，不用扯到sg函数的那种。
t1：
Description
被污染的灰灰草原上有羊和狼。有N只动物围成一圈，每只动物是羊或狼。
该游戏从其中的一只动物开始，报出[1,K]区间的整数，若上一只动物报出的数是x，下一只动物可以报[x+1,x+K]区间的整数，游戏按顺时针方向进行。每只动物报的数字都不能超过M。若一只动物报了M这个数，它所在的种族就输了。问以第i只动物为游戏的开始，最后哪种动物会赢？
该游戏从其中的一只动物开始，报出[1,K]区间的整数，若上一只动物报出的数是x，下一只动物可以报[x+1,x+K]区间的整数，游戏按顺时针方向进行。每只动物报的数字都不能超过M。若一只动物报了M这个数，它所在的种族就输了。问以第i只动物为游戏的开始，最后哪种动物会赢？
Input
第一行输入三个正整数N，M，K。
接下来一行N个正整数，分别表示N只动物的种类，以顺时针的方向给出。0代表羊，1代表狼。
接下来一行N个正整数，分别表示N只动物的种类，以顺时针的方向给出。0代表羊，1代表狼。
Output
一行输出N个整数，表示若从第i只动物开始，赢的动物的种类。同上，0代表羊，1代表狼。
就是dp,f[i][j]表示第i个动物报数最大为j是否必胜。然后加一个后缀和（应该能叫后缀和吧）（或者说区间和？）优化。
中间还wa了一次，因为在处理s数组时减去的那个f数组越界了，需要特判一下。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,kk;
int f[10010][5010],a[10010],s[10010][5010];
int main()
{
freopen("vode.in","r",stdin);
freopen("vode.out","w",stdout);
scanf("%d%d%d",&n,&m,&kk);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int p=1;
for(int i=n+1;i<=n+m;i++)
{
if(p>n)
p=1;
a[i]=a[p];
p++;
}
for(int i=n+m-1;i>=1;i--)
for(int j=m-1;j>=1;j--)
{
if(a[i]==a[i+1])
{
s[i][j]=s[i][j+1];
if(j+kk<m)
s[i][j]-=f[i][j+kk];
if(s[i+1][j+1]>0)
{
f[i][j]=1;
s[i][j]++;
}
}
else
{
s[i][j]=s[i][j+1];
if(j+kk<m)
s[i][j]-=f[i][j+kk];
if(s[i+1][j+1]==0)
{
f[i][j]=1;
s[i][j]++;
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=kk;j++)
if(f[i][j])
{
printf("%d ",a[i]);
break;
}
else if(j==kk)
{
printf("%d ",a[i]^1);
}
fclose(stdin);
fclose(stdout);
return 0;
}
不想改a组了，先写了一个b组t3玩。
Description
话说， 小X是个数学大佬，他喜欢做数学题。有一天，小X想考一考小Y。他问了小Y一道数学题。题目如下：
对于一个正整数N，存在一个正整数T（0<T<N），使得
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD4AAABECAYAAADZeIbjAAADRUlEQVR4nO2aMXKjMBSGf3ZyFG8KT04AJ7DduHKbTpROs11Kd2lwmXRpt6IJnMA+gceF4S5ayQYvBqEgGYF24ZuRCzPw+JH03pP0HMrAAPnR9wv0xSh8aNgnPPbhOA782KwZi4Sn2HoOnPlHJ9YsEj7BekdBkwBuB9YsEt4to/ChMQofGqPwoVEVnm7hscyJZ0+Ot2VpRfmyd7mWNdMZVj0x/MJ7iJuHbVlADq0jIny5SklUc80NaFJ7sx4RwdnmtclslN4hCVx2D6F/XzeiRHJ/rfCIuNR1xca5EeEH6ZCIFEUmNKi8a0SDoL5raoSzBwVR1usuvb2fGykatQHWu2yEuBKhZcTOLf3CET+B2RIEe7y8FSdywq5N+VV7iEPwpc3T46TxLWLhCTBd8IfM8IuNIXyEuEpnRg6rBZqbME96OrBfguWs+T1C4XF4RP7xJutX9sgPbDL3mJ6A1cIq2fj6vWczUm0UCoSnON0M5RmWbALtX95Yr3MjQN2Iiv3vwosDrza+6MKmHtetOgorsz4JKCk7Cfafew5tzIm07M4BNG5CZGFXQrXHk2O1SycLrPhUn89xmLbr1uglsjRqInTmd264gCRUCUNb31zCGDRG4VX4JfPJh5VIIPsopP1sTY8sYSlNBRX9Dv+5Y6T+s4yrMzvItpiv4c+HqcWfRcK56GfgM/fi0TlxmpsSb8j7qBMFVYea5Q8qi4+m2NPjszXW5dRr8ognQ+bsEV6La2RtYHc44weI4RL0XTUt+56H1p/YGszZbYBo175ojrXCY597+B3MyLZUON/JDZc7vBtc9lvn3LjoZ3yiOK3TrV+/TaxL6wHyDm4XSg23mTWxRnhlT73QTCQwdoczg1g3x7vi7NX5Suh/pzywH0R/DoHBDvVR+NAYhTei82qJO6seZGilPV1VS9xZ9SBDa6jH4QEuP1LaCHr9dAB5XbdyjByHfD2eP0t8KjrVPbJW/1Z9VUuoVz3IUO/xvqolNKoeZKgL76laQvtUtAZl4f1US+hVPchQFN5XtYRm1YMMJY/QcbXEFc2qBxlqPd5xtURO2/P7TPNv1Fe1hH7Vg4xGwvuplri/6kHGuOc2NEbhQ2MUPjRG4UPjD4ped/B8yB0SAAAAAElFTkSuQmCC" alt=" " />
的值是正整数。
小X给出N，让小Y给出所有可能的T。如果小Y不回答这个神奇的大佬的简单数学题,他学神的形象就会支离破碎。所以小Y求你帮他回答小X的问题。
对于一个正整数N，存在一个正整数T（0<T<N），使得
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD4AAABECAYAAADZeIbjAAADRUlEQVR4nO2aMXKjMBSGf3ZyFG8KT04AJ7DduHKbTpROs11Kd2lwmXRpt6IJnMA+gceF4S5ayQYvBqEgGYF24ZuRCzPw+JH03pP0HMrAAPnR9wv0xSh8aNgnPPbhOA782KwZi4Sn2HoOnPlHJ9YsEj7BekdBkwBuB9YsEt4to/ChMQofGqPwoVEVnm7hscyJZ0+Ot2VpRfmyd7mWNdMZVj0x/MJ7iJuHbVlADq0jIny5SklUc80NaFJ7sx4RwdnmtclslN4hCVx2D6F/XzeiRHJ/rfCIuNR1xca5EeEH6ZCIFEUmNKi8a0SDoL5raoSzBwVR1usuvb2fGykatQHWu2yEuBKhZcTOLf3CET+B2RIEe7y8FSdywq5N+VV7iEPwpc3T46TxLWLhCTBd8IfM8IuNIXyEuEpnRg6rBZqbME96OrBfguWs+T1C4XF4RP7xJutX9sgPbDL3mJ6A1cIq2fj6vWczUm0UCoSnON0M5RmWbALtX95Yr3MjQN2Iiv3vwosDrza+6MKmHtetOgorsz4JKCk7Cfafew5tzIm07M4BNG5CZGFXQrXHk2O1SycLrPhUn89xmLbr1uglsjRqInTmd264gCRUCUNb31zCGDRG4VX4JfPJh5VIIPsopP1sTY8sYSlNBRX9Dv+5Y6T+s4yrMzvItpiv4c+HqcWfRcK56GfgM/fi0TlxmpsSb8j7qBMFVYea5Q8qi4+m2NPjszXW5dRr8ognQ+bsEV6La2RtYHc44weI4RL0XTUt+56H1p/YGszZbYBo175ojrXCY597+B3MyLZUON/JDZc7vBtc9lvn3LjoZ3yiOK3TrV+/TaxL6wHyDm4XSg23mTWxRnhlT73QTCQwdoczg1g3x7vi7NX5Suh/pzywH0R/DoHBDvVR+NAYhTei82qJO6seZGilPV1VS9xZ9SBDa6jH4QEuP1LaCHr9dAB5XbdyjByHfD2eP0t8KjrVPbJW/1Z9VUuoVz3IUO/xvqolNKoeZKgL76laQvtUtAZl4f1US+hVPchQFN5XtYRm1YMMJY/QcbXEFc2qBxlqPd5xtURO2/P7TPNv1Fe1hH7Vg4xGwvuplri/6kHGuOc2NEbhQ2MUPjRG4UPjD4ped/B8yB0SAAAAAElFTkSuQmCC" alt=" " />
的值是正整数。
小X给出N，让小Y给出所有可能的T。如果小Y不回答这个神奇的大佬的简单数学题,他学神的形象就会支离破碎。所以小Y求你帮他回答小X的问题。
Input
一个整数N。
Output
第一个数M，表示对于正整数N，存在M个不同的正整数T，使得
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD4AAABECAYAAADZeIbjAAADRUlEQVR4nO2aMXKjMBSGf3ZyFG8KT04AJ7DduHKbTpROs11Kd2lwmXRpt6IJnMA+gceF4S5ayQYvBqEgGYF24ZuRCzPw+JH03pP0HMrAAPnR9wv0xSh8aNgnPPbhOA782KwZi4Sn2HoOnPlHJ9YsEj7BekdBkwBuB9YsEt4to/ChMQofGqPwoVEVnm7hscyJZ0+Ot2VpRfmyd7mWNdMZVj0x/MJ7iJuHbVlADq0jIny5SklUc80NaFJ7sx4RwdnmtclslN4hCVx2D6F/XzeiRHJ/rfCIuNR1xca5EeEH6ZCIFEUmNKi8a0SDoL5raoSzBwVR1usuvb2fGykatQHWu2yEuBKhZcTOLf3CET+B2RIEe7y8FSdywq5N+VV7iEPwpc3T46TxLWLhCTBd8IfM8IuNIXyEuEpnRg6rBZqbME96OrBfguWs+T1C4XF4RP7xJutX9sgPbDL3mJ6A1cIq2fj6vWczUm0UCoSnON0M5RmWbALtX95Yr3MjQN2Iiv3vwosDrza+6MKmHtetOgorsz4JKCk7Cfafew5tzIm07M4BNG5CZGFXQrXHk2O1SycLrPhUn89xmLbr1uglsjRqInTmd264gCRUCUNb31zCGDRG4VX4JfPJh5VIIPsopP1sTY8sYSlNBRX9Dv+5Y6T+s4yrMzvItpiv4c+HqcWfRcK56GfgM/fi0TlxmpsSb8j7qBMFVYea5Q8qi4+m2NPjszXW5dRr8ognQ+bsEV6La2RtYHc44weI4RL0XTUt+56H1p/YGszZbYBo175ojrXCY597+B3MyLZUON/JDZc7vBtc9lvn3LjoZ3yiOK3TrV+/TaxL6wHyDm4XSg23mTWxRnhlT73QTCQwdoczg1g3x7vi7NX5Suh/pzywH0R/DoHBDvVR+NAYhTei82qJO6seZGilPV1VS9xZ9SBDa6jH4QEuP1LaCHr9dAB5XbdyjByHfD2eP0t8KjrVPbJW/1Z9VUuoVz3IUO/xvqolNKoeZKgL76laQvtUtAZl4f1US+hVPchQFN5XtYRm1YMMJY/QcbXEFc2qBxlqPd5xtURO2/P7TPNv1Fe1hH7Vg4xGwvuplri/6kHGuOc2NEbhQ2MUPjRG4UPjD4ped/B8yB0SAAAAAElFTkSuQmCC" alt=" " />
是整数。
后面是M个数，每一个数代表可能的正整数T（按从小到大的顺序排列）。
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD4AAABECAYAAADZeIbjAAADRUlEQVR4nO2aMXKjMBSGf3ZyFG8KT04AJ7DduHKbTpROs11Kd2lwmXRpt6IJnMA+gceF4S5ayQYvBqEgGYF24ZuRCzPw+JH03pP0HMrAAPnR9wv0xSh8aNgnPPbhOA782KwZi4Sn2HoOnPlHJ9YsEj7BekdBkwBuB9YsEt4to/ChMQofGqPwoVEVnm7hscyJZ0+Ot2VpRfmyd7mWNdMZVj0x/MJ7iJuHbVlADq0jIny5SklUc80NaFJ7sx4RwdnmtclslN4hCVx2D6F/XzeiRHJ/rfCIuNR1xca5EeEH6ZCIFEUmNKi8a0SDoL5raoSzBwVR1usuvb2fGykatQHWu2yEuBKhZcTOLf3CET+B2RIEe7y8FSdywq5N+VV7iEPwpc3T46TxLWLhCTBd8IfM8IuNIXyEuEpnRg6rBZqbME96OrBfguWs+T1C4XF4RP7xJutX9sgPbDL3mJ6A1cIq2fj6vWczUm0UCoSnON0M5RmWbALtX95Yr3MjQN2Iiv3vwosDrza+6MKmHtetOgorsz4JKCk7Cfafew5tzIm07M4BNG5CZGFXQrXHk2O1SycLrPhUn89xmLbr1uglsjRqInTmd264gCRUCUNb31zCGDRG4VX4JfPJh5VIIPsopP1sTY8sYSlNBRX9Dv+5Y6T+s4yrMzvItpiv4c+HqcWfRcK56GfgM/fi0TlxmpsSb8j7qBMFVYea5Q8qi4+m2NPjszXW5dRr8ognQ+bsEV6La2RtYHc44weI4RL0XTUt+56H1p/YGszZbYBo175ojrXCY597+B3MyLZUON/JDZc7vBtc9lvn3LjoZ3yiOK3TrV+/TaxL6wHyDm4XSg23mTWxRnhlT73QTCQwdoczg1g3x7vi7NX5Suh/pzywH0R/DoHBDvVR+NAYhTei82qJO6seZGilPV1VS9xZ9SBDa6jH4QEuP1LaCHr9dAB5XbdyjByHfD2eP0t8KjrVPbJW/1Z9VUuoVz3IUO/xvqolNKoeZKgL76laQvtUtAZl4f1US+hVPchQFN5XtYRm1YMMJY/QcbXEFc2qBxlqPd5xtURO2/P7TPNv1Fe1hH7Vg4xGwvuplri/6kHGuOc2NEbhQ2MUPjRG4UPjD4ped/B8yB0SAAAAAElFTkSuQmCC" alt=" " />
是整数。
后面是M个数，每一个数代表可能的正整数T（按从小到大的顺序排列）。
就是把式子化简一下，设比值为k，然后会发现T=(2K-2)/(2K-1)*N,我们要让t为正整数，同时（2K-2）/(2K-1)又不能为一，2k-1就一定为n的因子。k为正整数，所以2k-1为奇数，然后就可以n½枚举找n的奇因子了。注意一下2k-2不能为零，也就是2k-1不能为1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,a[1000010],cnt;
int main()
{
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
scanf("%lld",&n);
long long sn=sqrt(n);
for(long long i=1;i<=sn;i++)
if(!(n%i))
{
if((i%2)&&i!=1)
a[++cnt]=(n/i)*(i-1);
if((n/i)%2&&(n/i)!=1)
a[++cnt]=i*(n/i-1);
}
cout<<cnt<<" ";
sort(a+1,a+1+cnt);
for(int i=1;i<=cnt;i++)
printf("%lld ",a[i]);
fclose(stdin);
fclose(stdout);
return 0;
}
然后我终于改了a组t2：
Description
有一副n*m的地图，有n*m块地，每块是下列四种中的一种：
墙：用#表示，墙有4个面，分别是前面，后面，左面，右面。
起点：用C表示，为主角的起点，是一片空地。
终点：用F表示，为主角的目的地，是一片空地。
空地：用 . 表示。
其中除了墙不能穿过，其他地方都能走。
主角有以下3种操作：
1.移动到相邻的前后左右的地方，花费一个单位时间。
2.向前后左右其中一个方向发射子弹，子弹沿直线穿过，打在最近的一堵墙的一面，然后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口，若出现有3个开口，出现时间最早的开口会立即消失。该操作不用时间。
3.可以从一个与开口相邻的空地跳进去，进入秘密通道，从另外一个开口正对的空地跳出来。这个过程花费一个单位时间。
墙：用#表示，墙有4个面，分别是前面，后面，左面，右面。
起点：用C表示，为主角的起点，是一片空地。
终点：用F表示，为主角的目的地，是一片空地。
空地：用 . 表示。
其中除了墙不能穿过，其他地方都能走。
主角有以下3种操作：
1.移动到相邻的前后左右的地方，花费一个单位时间。
2.向前后左右其中一个方向发射子弹，子弹沿直线穿过，打在最近的一堵墙的一面，然后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口，若出现有3个开口，出现时间最早的开口会立即消失。该操作不用时间。
3.可以从一个与开口相邻的空地跳进去，进入秘密通道，从另外一个开口正对的空地跳出来。这个过程花费一个单位时间。
地图四周都是墙，问主角最少用多少时间从C走到F。C和F
只会出现一次。
Input
第一行输入两个正整数n，m。
接下来n行，每行m个字符描述地图。
接下来n行，每行m个字符描述地图。
Output
输出1个整数，表示最短时间完成路途。如果无解输出nemoguce
我当时打了bfs，然后愉悦爆零。哇的一下哭出声。
这个题是把每一个非墙点与相邻点连边权为1的边，然后找到四个方向的墙，连一条边权为min（dis（此点，墙边传送门的点））+1的边（其实和最近的传送门点应该连边权为dis的边，但可以从边权为1的边走过去，不影响答案）。然后跑spfa，求起点到终点最短路即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,s,t,cnt,head[250010],dis[250010],vis[250010];
char mp[510][510];
struct Edge
{
int v,nxt,val;
}e[10000010];
void add(int u,int v,int val)
{
e[++cnt].v=v;
e[cnt].nxt=head[u];
e[cnt].val=val;
head[u]=cnt;
}
int num(int x,int y)
{
return (x-1)*m+y;
}
void spfa()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
queue<int>q;
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].val)
{
dis[v]=dis[u]+e[i].val;
if(!vis[v])
{
q.push(v);
vis[v]=1;
}
}
}
}
}
int main()
{
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='C')
s=num(i,j);
else if(mp[i][j]=='F')
t=num(i,j);
}
for(int i=2;i<n;i++)
for(int j=2;j<m;j++)
if(mp[i][j]!='#')
{
int x1=i,x2=i,y1=j,y2=j;
int mindis=0x3f3f3f3f;
while(mp[x1+1][j]!='#')
x1++;
while(mp[x2-1][j]!='#')
x2--;
while(mp[i][y1+1]!='#')
y1++;
while(mp[i][y2-1]!='#')
y2--;
mindis=min(x1-i,min(i-x2,min(y1-j,j-y2)));
mindis++;
add(num(i,j),num(x1,j),mindis);
add(num(i,j),num(x2,j),mindis);
add(num(i,j),num(i,y1),mindis);
add(num(i,j),num(i,y2),mindis);
if(mp[i+1][j]!='#')
add(num(i,j),num(i+1,j),1);
if(mp[i-1][j]!='#')
add(num(i,j),num(i-1,j),1);
if(mp[i][j+1]!='#')
add(num(i,j),num(i,j+1),1);
if(mp[i][j-1]!='#')
add(num(i,j),num(i,j-1),1);
}
spfa();
if(dis[t]==0x3f3f3f3f)
cout<<"nemoguce";
else
cout<<dis[t];
fclose(stdin);
fclose(stdout);
return 0;
}
其实题目不是不可做，就是考试死活想不到正路上......dalao炒鸡多啊我的天，orz。
然而我还是改完了t3：
Description
有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。
Input
第一行输入三个正整数n,m,q，其中q表示询问个数。
接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。
接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。
Output
输出q行，每行一个正整数，表示最早连通的天数
并查集，按秩合并，把时间赋为点权（我之前纠结了半天怎么连边权2333），在并查集树上找max点权就行。
re了好几次，最后发现freopen文件名打错了......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,q,fa[100010],dep[100010],siz[100010],tim[100010],x,y;
int find_fa(int x)
{
if(fa[x]==x)
return x;
return find_fa(fa[x]);
}
void update(int x)
{
if(fa[x]==x)
return;
update(fa[x]);
dep[x]=dep[fa[x]]+1;
}
int query(int a,int b)
{
int res=0;
if(dep[a]<dep[b])
swap(a,b);
while(dep[a]>dep[b])
{
res=max(res,tim[a]);
a=fa[a];
}
while(a!=b)
{
res=max(res,max(tim[a],tim[b]));
a=fa[a];
b=fa[b];
}
return res;
}
int main()
{
freopen("pictionary.in","r",stdin);
freopen("pictionary.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
fa[i]=i,siz[i]=1;
for(int i=1;i<=m;i++)
{
int r=n/(m-i+1);
int p=m-i+1;
for(int j=2;j<=r;j++)
{
int f1=find_fa(p*(j-1));
int f2=find_fa(p*j);
if(f1!=f2)
{
if(siz[f1]<siz[f2])
swap(f1,f2);
fa[f2]=f1;
tim[f2]=i;
siz[f1]=max(siz[f1],siz[f2]+1);
}
}
}
for(int i=1;i<=n;i++)
update(i);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y));
}
fclose(stdin);
fclose(stdout);
return 0;
}
