cf Round #766(Div. 2)
B
Description
n*m个方格，一个人尽量往中间坐没涂色的格子，另一个人往四角坐，求涂上0,1,2,...,n*m-1个格子后两人曼哈顿距离的最大值。
Solution
看到曼哈顿距离，会自然而然考虑将(x,y)对称到左上角(x',y')后的x'+y'。
按x'+y'升序排序后即为涂色的顺序。相同x'+y'涂色后的答案相同。
只剩一个格子没涂色时答案为dis((1,1),(n,m))。x'+y'减k则答案也减k。
#include
using namespace std;
const int N=100005;
struct grid{
int x,y,ans;
}a[N];
int n,m,t,cnt;
int dis(grid a){
return min(a.x-1,n-a.x)+min(a.y-1,m-a.y);
}
bool cmp_xy(grid a,grid b){
return dis(a)>dis(b);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
cnt=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
a[++cnt].x=i;a[cnt].y=j;
}
sort(a+1,a+1+cnt,cmp_xy);
for(int i=cnt,ans=(n-1)+(m-1);i;--i){
if(i C
Description
一棵树，求给每条边赋权值使任意长度\(\leq2\)的路径权值和都为质数。
Solution
由于质数的奇偶性，所以当某个点的度>2时无解。
由于保证连通性，所以树是一条链。交替填入2,5即可。
#include
using namespace std;
const int N=100005;
struct graph{
int nxt,to,w;
}e[N<<1];
int g[N],deg[N],n,t,cnt;
void adde(int x,int y){
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].w=0;
}
void dfs(int u,int num){
for(int i=g[u];i;i=e[i].nxt)
if(!e[i].w){
e[i].w=e[i^1].w=(num==2?5:2);
dfs(e[i].to,e[i].w);
}
}
int main(){
scanf("%d",&t);
while(t--){
cnt=1;
memset(g,0,sizeof(g));
memset(deg,0,sizeof(deg));
scanf("%d",&n);
for(int i=1,x,y;i2){
flag=false;break;
}
if(!flag){
printf("-1\n");continue;
}
for(int i=1;i<=n;++i)
if(deg[i]==1){
dfs(i,2);
}
for(int i=1;i D
Description
给定一组互不相同的数，往里面一直加入任意两个数的gcd直到不能加入为止。求加入的数的个数。
Solution
最开始想的是如何处理加入一个新数带来的变化。
后来发现结果是确定的只用考虑每个数是否会存在于结果中即可。
由于gcd(n,m) 一个数k存在的条件是存在两个数a,b，是>k的k的倍数且a/k与b/k互质，即gcd(a,b)=k。 埃氏筛处理即可。 Description
又因为所有>k的k的倍数\(a_i\)满足\(gcd(a_1,...,a_n)\geq k\)，所以如果存在a,b，\(gcd(a_1,...,a_n)= k\)。#includeE
一栋楼，同层之间可以平移，会损失体力，不同层之间可以到特定位置走梯子，会收获体力（梯子只能往上走）。求(1,1)到(n,m)的最小损失体力值。
Solution
离散化所有梯子的起点和终点以及(1,1)和(n,m)。
dis[i]表示到达i点的最小损失体力值。
很显然的是，不同层之间独立，从下往上考虑每一层。
每一层中，一个点到另一个点直达最优，所以可以两个方向分别扫一遍求出dis[i]。
然后再更新以这一层为起点的梯子能到达的dis[i]。#include