A
构造题
有一个44的方格 每次放入一个横向12或竖向2*1的方格
满了一行或一列就会消掉
求方案
不放最后一行 这样竖行就不会消
然后竖着的放前两行 横着的放第三行 循环放就可以啦
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
const int N = 1e3 + 5;
using namespace std;
const int r[2][2] = {{3, 1}, {3, 3}};
const int c[4][2] = {{1, 1}, {1, 2}, {1, 3}, {1, 4}};
char str[N];
int main(){
scanf("%s", str + 1);
int len = strlen(str + 1);
int cntr = 0, cntc = 0;
for(int i = 1; i <= len; ++i){
if(str[i] == '1'){
printf("%d %d
", r[cntr][0], r[cntr][1]);
++cntr; if(cntr >= 2) cntr -= 2;
}
else {
printf("%d %d
", c[cntc][0], c[cntc][1]);
++cntc; if(cntc >= 4) cntc -= 4;
}
}
return 0;
}
B
这是一道交互题
有一个数a 现在你每次可以询问"? x y"
如果(x mod a >= y mod a) 那么返回"x" 否则返回"y"
如果得出结果 就输出"! a" a是猜到的值
多数据 每轮以start开头 end表示结束
每轮询问不能超过60次
(a leq 1e9)
首先考虑特判1
用"? 0 1"就可以 （x表示是1）
现在已经知道不是1了 就用"? 1 2"来判
显然如果a == 2那么返回x
如果a >= 3那么返回y
依此类推 倍增就好啦 注意每次询问是左开右闭的
扩大到(x le a leq y)时 用同样的方法每次收拢(frac{y - x}{2})个就好啦
直到y - x == 1此时y就是答案
1e9 < 2 ^ 30
再加上第一次特判 显然可过
C
给你一张没有重边自环的n个点m条边的无向图 还有一个常数k
保证每个点度数至少为3
要求完成下列任务之一即可 如果都无解输出-1
任务一：找到一条长度至少为(lfloor frac{n}{k}
floor)的路径
任务二：找到k个环 每个环要求满足：
- 1 长度至少为3
- 2 长度不是3的倍数
- 3 这个环里必须至少有一个点满足它只属于这个环 不属于其他环
(n, k leq 2.5 * 10^5 m leq 5 * 10^5)
HINT 标签：constructive algorithms, dfs and similar
首先任务一很好办啊 bfs一下纪录father就可以了
如果没有的话 任务二中显然如果有两个环有公共边 那么这两个环上的点都不能做representative - vertex
先把这张图tarjan一波
对于一个双连通分量 如果其中不是割点的点度数有大于2的 那么说明有多环
所以我们在找到一个强连通分量的时候
如果这个bc里面（所有点都是割点并且这些割点都不是单独的） 或者有不是割点的点度数大于2 那么弃掉它
否则这整个就是一个环（或者单点） 判断它是不是(size geq 3)
如果是就可以输出
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
const int N = 5e5 + 5;
using namespace std;
struct Edge{
int v, next;
}edge[N << 1];
int head[N], esize;
inline void addedge(int x, int y){
edge[++esize] = (Edge){y, head[x]}; head[x] = esize;
}
int n, m, k;
int dfn[N], tim, dis[N], fa[N], mx;
vector<int> cyc, leaf, son;
bool vis[N];
void dfs(int x, int ff){
dfn[x] = ++tim, dis[x] = dis[ff] + 1, fa[x] = ff;
if(dis[mx] < dis[x]) mx = x;
vis[x] = 1;
bool lf = 1;
for(int i = head[x], vv; ~i; i = edge[i].next){
vv = edge[i].v; if(vis[vv]) continue;
dfs(vv, x);
lf = 0;
}
if(lf) leaf.push_back(x);
}
int main(){
memset(head, -1, sizeof(head));
scanf("%d%d%d", &n, &m, &k);
for(int i = 1, x, y; i <= m; ++i){
scanf("%d%d", &x, &y);
addedge(x, y), addedge(y, x);
}
dfs(1, 0);
if(dis[mx] > (n / k)){
printf("PATH
%d
", dis[mx]);
while(mx)
printf("%d ", mx), mx = fa[mx];
}
else {
printf("CYCLES
");
int cnt = 0;
for(auto i : leaf){
son.clear(); cyc.clear();
for(int j = head[i]; ~j; j = edge[j].next) if(edge[j].v != fa[i]) son.push_back(edge[j].v);
if((dis[i] - dis[son[0]]) % 3 != 2){
//printf("%d %d
", dis[i], dis[son[0]]);
int j = i;
while(j != son[0]) cyc.push_back(j), j = fa[j];
cyc.push_back(j);
}
else if((dis[i] - dis[son[1]]) % 3 != 2){
int j = i;
while(j != son[1]) cyc.push_back(j), j = fa[j];
cyc.push_back(j);
}
else {
//printf("*");
if(dis[son[0]] < dis[son[1]]) swap(son[0], son[1]);
cyc.push_back(i);
int j = son[0];
while(j != son[1]) cyc.push_back(j), j = fa[j];
cyc.push_back(j);
}
printf("%d
", cyc.size());
for(auto j : cyc) printf("%d ", j);
printf("
");
if(++cnt == k) break;
}
}
return 0;
}
D
这道题如果所有数的最大公约数为一
那当然不用管了 输出零就好
(2 * 3 * 5 * 7 * 11 * ... * 31 = 200560490130 ge 10^12)
这样的话最多gcd有11种质因数
那么对于一种质因数 要消掉它的话 就要把任一个数消掉这种这种质因数
所以这么说最多只需要消掉11个数
只有十一个？ 考虑状压dp
f[i][S] = 最小的被消掉的数的权值之和 之所以有i那一位是为了统计用了多少个数 就像背包一样
有可能一个数被消掉的不只是一个质因数 那怎么办？
这个时候我们先处理出这个数中(gcd包含的那些质因数)的幂的乘积
也可以把它塞进一个map 这样是为了不重复处理一个数的质因数集合