给n个数，求其中能满足 a[i] % a[j] == 0 的数对之和
n = 1W，max_ai = 100W 不是很大，所以就直接筛就可以了
计算可得最高复杂度 < 1kW
...考场上写了这个解法，结果把 j += i 写成了 j ++ ...
我还以为是单个测试点case太多...多么痛的领悟...
#include <bits/stdc++.h>
using namespace std;
int Case, n, m, k, a[], b[];
int main() {
scanf("%d", &Case);
while(Case --) {
m = , k = ;
scanf("%d", &n);
for(int i = ;i <= n;i ++) scanf("%d", &a[i]), b[a[i]] ++, k = max(k, a[i]);
for(int i = ;i <= k;i ++) {
if(!b[i]) continue;
m += b[i] * (b[i] - ) / ;
for(int j = i << ;j <= k;j += i)
m += b[j] * b[i];
}
printf("%d\n", m);
for(int i = ;i <= n;i ++) b[a[i]] --;
}
return ;
}H.Paint it really, really dark gray
之前写过...但因为清楚记得之前调了一段时间...最后时间不是很多就去看D了...迷
假如递归过程中，当前节点的子节点都是叶子节点，那么只要访问一下需要染色的节点再回来就可以了
这样它的子节点都满足要求了，那么当前节点就可以看作是叶子节点了，然后处理上一层...
#include <bits/stdc++.h>
using namespace std;
int n, a[], v[];
vector <int> e[], ans;
bool d[];
void dfs(int x) {
a[x] = d[x] = (a[x] == -), v[x] = ;
for(int i = ;i < e[x].size();i ++) {
if(v[e[x][i]]) continue;
dfs(e[x][i]);
d[x] |= d[e[x][i]];
}
}
void dfs_(int x, int f) {
a[x] ^= , ans.push_back(x);
for(int i = ;i < e[x].size();i ++) {
if(e[x][i] == f) continue;
if(d[e[x][i]]) dfs_(e[x][i], x), ans.push_back(x), a[x] ^= ;
}
if(a[x] && x != ) ans.push_back(f), ans.push_back(x), a[f] ^= , a[x] ^= ;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = ;i <= n;i ++) cin >> a[i];
int u, v;
for(int i = ;i < n;i ++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(), dfs_(, );
for(auto it : ans) printf("%d ", it);
if(!a[]) printf("%d 1 %d", e[][], e[][]);
return ;
}数据范围其实不大，对于不止一种解的解决办法
就暴力测试每一个 '?' 就可以了
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j;i <= k;i ++)
int n, m, sx, sy, cnt, lcnt, last;
char s[][];
int mmp[][];
const int xx[] = {, , , -};
const int yy[] = {, -, , };
void dfs(int x, int y, int nx = , int ny = ) {
cnt ++;
rep(i, , ) {
nx = x + xx[i], ny = y + yy[i];
if(nx > && nx <= n && ny > && ny <= m && s[nx][ny] != '#' && !mmp[nx][ny]) {
mmp[nx][ny] = ;
if(s[nx][ny] == '?') s[nx][ny] = '!';
dfs(nx, ny);
}
}
}
int main() {
scanf("%d %d", &n, &m);
rep(i, , n) scanf("%s", s[i] + );
rep(i, , n) rep(j, , m)
if(s[i][j] == '.' && !mmp[i][j]) {
lcnt ++, sx = i, sy = j;
if(lcnt == ) {
puts("Impossible");
return ;
}
mmp[i][j] = , dfs(i, j);
}
last = cnt;
rep(i, , n) rep(j, , m) {
if(s[i][j] == '?') s[i][j] = '#';
else if(s[i][j] == '!') {
s[i][j] = '#', cnt = ;
memset(mmp, , sizeof mmp);
mmp[sx][sy] = , dfs(sx, sy);
if(cnt + == last) {
puts("Ambiguous");
return ;
}
else s[i][j] = '.';
}
}
rep(i, , n) puts(s[i] + );
return ;
}