A
首先筛质数,方便后面直接判断某个数是否为合数。
如果几个数的和为合数,则直接输出
如果为质数,那么一定为奇数,那么这几个数中一定有奇数,减掉这个数后即为合数
也就是说答案要么为n,要么为n-1,我就写了个判断,然后按需输出即可。
#include<bits/stdc++.h>
using namespace std;
bool prim[20020];
int main()
{
int t; cin >> t;
for(int i = 2; i <= 2e4; i ++) prim[i] = true;
for(int i = 2; i <= 2e4; i ++)
if(prim[i])
for(int j = i << 1; j <= 2e4; j += i) prim[j] = false;
while(t --)
{
int n, tot = 0; cin >> n;
vector<int> a(n);
for(auto & x : a) cin >> x, tot += x;
if(!prim[tot])
{
cout << n << endl;
for(int i = 1; i <= n; i ++) cout << i << ' ';
cout << endl;
}
else
{
for(int i = 0; i < n; i ++)
if(!prim[tot - a[i]])
{
cout << n - 1 << endl;
for(int j = 0; j < n; j ++)
if(i != j) cout << j + 1 << ' ';
cout << endl;
break;
}
}
}
}
B
菊花图精辟。
如果我们画一个菊花,也就是所有点和同一个点相连,那么遍历任意三个外围的点的路径就是:外围,中心,外围,中心,外围。如果把中心放在起点或者终点也需要走重复的路径。
所以我看了一下数据范围,m<n,那么一定有个点没有在b的位置出现过,把它作为中心一定满足所有条件。
#include<bits/stdc++.h>
using namespace std;
bool prim[20020];
int main()
{
int t; cin >> t;
while(t --)
{
int n, m; cin >> n >> m;
int a, b, c;
bool st[n] = {false};
for(int i = 1; i <= m; i ++)
cin >> a >> b >> c, st[--b] = true;
for(int i = 0; i < n; i ++)
if(!st[i])
{
for(int j = 0; j < n; j ++)
if(i != j) cout << i + 1 << ' ' << j + 1 << endl;
break;
}
}
}
C
题意是,先告诉你.X图,你可以就此推出EN图,问你据此EN图能否唯一确定.X图。
思路是如果存在
? X
X ?
的情况,得出来的EN图就是
? N
N N
左上角的?不影响,右下角的?无论是’.’还是’X’,都得到N,那么这个EN图就不能回去唯一确定.X图,所以就要输出NO
代码就统计一下每个位置会不会有这样斜的X,然后用前缀和优化或者把bad_position放vector里面用lower_bound什么的都行
#include<bits/stdc++.h>
using namespace std;
bool prim[20020];
int main()
{
int n, m; cin >> n >> m;
char g[n][m];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
cin >> g[i][j];
int un[m + 1] = {0};
for(int i = 1; i < n; i ++)
for(int j = 0; j < m - 1; j ++)
if(g[i][j] == 'X' && g[i - 1][j + 1] == 'X')
un[j + 1] ++;
for(int j = 1; j <= m; j ++) un[j] += un[j - 1];
int q, l, r; cin >> q;
while(q --)
{
cin >> l >> r;
cout << (un[r - 1] == un[l - 1] ? "YES\n" : "NO\n");
}
}
D
permutation的特点在于各个数都不相同,所以如果所有数同时+1,那么结果也各不相同。
我们以最后一个数为基准,让它+1,以此让前面所有数统一+1~n,举个例子,最后一个数+1,前面的数都+5,结果是3,那就是第3个数比最后一个数大(1-5)也就是小4.这样我们可以得到1到n-1里所有比最后一个数小的数的下标和差值,同理让最后一个数+n再来一次也可以得到前面所有比它大的数的下标和差值,综合到一起得到整个排列。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
int num[n + 1] = {0};
for(int i : {1, n})
for(int j = 1; j <= n; j ++)
{
cout << '?' << ' ';
for(int k = 1; k < n; k ++) cout << j << ' ';
cout << i << endl;
int seq; cin >> seq;
num[seq] = i - j;
}
int M = 0;
for(int i = 1; i <= n; i ++) M = max(M, num[i]);
for(int i = 1; i <= n; i ++) num[i] = n - M + num[i];
cout << '!' << ' ';
for(int i = 1; i <= n; i ++) cout << num[i] << ' ';
}
E
如果所有点被问偶数次,那么就是YES,因为我们可以构造一个树,让每次访问它都沿着这条树走。
如果有点被问奇数次,那么就是NO,因为与它相连的路径总和是奇数,就一定有一条路总和是奇数。
把两种情况综合到一起就是代码。
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int N = 3e5 + 10;
vector<int> h[N];
int p[N], st[N], qu[N], qv[N], t[N], d[N];
void dfs(int u)
{
st[u] = true;
for(auto x : h[u])
if(!st[x]) p[x] = u, d[x] = d[u] + 1, dfs(x);
}
signed main()
{
int n, m; cin >> n >> m;
int x, y;
for(int i = 1; i <= m; i ++)
cin >> x >> y, h[x].pb(y), h[y].pb(x);
d[1] = 1; dfs(1);
int res = 0, q; cin >> q;
for(int i = 1; i <= q; i ++) cin >> qu[i] >> qv[i], t[qu[i]] ++, t[qv[i]] ++;
for(int i = 1; i <= n; i ++) res += t[i] & 1;
if(res) cout << "NO\n" << res / 2;
else
{
cout << "YES";
for(int i = 1; i <= q; i ++)
{
x = qu[i], y = qv[i];
vector<int> out1, out2;
while(x != y)
if(d[x] > d[y]) out1.pb(x), x = p[x];
else out2.pb(y), y = p[y];
out1.pb(x);
reverse(out2.begin(), out2.end());
cout << endl << out1.size() + out2.size() << endl;
for(auto out : out1) cout << out << ' ';
for(auto out : out2) cout << out << ' ';
}
}
}
%%%%%%%%%%%%%%%%