D.

给n个数，求其中能满足 a[i] % a[j] == 0 的数对之和

n = 1W，max_ai = 100W 不是很大，所以就直接筛就可以了

计算可得最高复杂度 < 1kW

...考场上写了这个解法，结果把 j += i 写成了 j ++ ...

我还以为是单个测试点case太多...多么痛的领悟...

1 #include 
     
       2  3 using namespace std; 4  5 int Case, n, m, k, a[10010], b[1000010]; 6  7 int main() { 8     scanf("%d", &Case); 9     while(Case --) {10         m = 0, k = 0;11         scanf("%d", &n);12         for(int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[a[i]] ++, k = max(k, a[i]);13         for(int i = 2;i <= k;i ++) {14             if(!b[i]) continue;15             m += b[i] * (b[i] - 1) / 2;16             for(int j = i << 1;j <= k;j += i)17                 m += b[j] * b[i];18         }19         printf("%d\n", m);20         for(int i = 1;i <= n;i ++) b[a[i]] --;21     }22     return 0;23 }
     

 

H.

之前写过...但因为清楚记得之前调了一段时间...最后时间不是很多就去看D了...迷

假如递归过程中，当前节点的子节点都是叶子节点，那么只要访问一下需要染色的节点再回来就可以了

这样它的子节点都满足要求了，那么当前节点就可以看作是叶子节点了，然后处理上一层...

1 #include 
     
       2  3 using namespace std; 4  5 int n, a[200010], v[200010]; 6  7 vector 
      
        e[200010], ans; 8  9 bool d[200010];10 11 void dfs(int x) {12     a[x] = d[x] = (a[x] == -1), v[x] = 1;13     for(int i = 0;i < e[x].size();i ++) {14         if(v[e[x][i]]) continue;15         dfs(e[x][i]);16         d[x] |= d[e[x][i]];17     }18 }19 20 void dfs_(int x, int f) {21     a[x] ^= 1, ans.push_back(x);22     for(int i = 0;i < e[x].size();i ++) {23         if(e[x][i] == f) continue;24         if(d[e[x][i]]) dfs_(e[x][i], x), ans.push_back(x), a[x] ^= 1;25     }26     if(a[x] && x != 1) ans.push_back(f), ans.push_back(x), a[f] ^= 1, a[x] ^= 1; 27 }28 29 int main() {30     ios::sync_with_stdio(false);31     cin >> n;32     for(int i = 1;i <= n;i ++) cin >> a[i];33     int u, v;34     for(int i = 1;i < n;i ++) {35         cin >> u >> v;36         e[u].push_back(v);37         e[v].push_back(u);38     }39     dfs(1), dfs_(1, 0);40     for(auto it : ans) printf("%d ", it);41     if(!a[1]) printf("%d 1 %d", e[1][0], e[1][0]);42     return 0;43 }
      
     

 

A.

数据范围其实不大，对于不止一种解的解决办法

就暴力测试每一个 '?' 就可以了

1 #include 
     
       2  3 #define rep(i, j, k) for(int i = j;i <= k;i ++) 4  5 int n, m, sx, sy, cnt, lcnt, last; 6  7 char s[60][60]; 8  9 int mmp[60][60];10 11 const int xx[] = {
   0, 0, 1, -1};12 const int yy[] = {
   1, -1, 0, 0};13 14 void dfs(int x, int y, int nx = 0, int ny = 0) {15     cnt ++;16     rep(i, 0, 3) {17         nx = x + xx[i], ny = y + yy[i];18         if(nx > 0 && nx <= n && ny > 0 && ny <= m && s[nx][ny] != '#' && !mmp[nx][ny]) {19             mmp[nx][ny] = 1;20             if(s[nx][ny] == '?') s[nx][ny] = '!';21             dfs(nx, ny);22         }23     }24 }25 26 int main() {27     scanf("%d %d", &n, &m);28     rep(i, 1, n) scanf("%s", s[i] + 1);29     rep(i, 1, n) rep(j, 1, m) 30         if(s[i][j] == '.' && !mmp[i][j]) {31             lcnt ++, sx = i, sy = j;32             if(lcnt == 2) {33                 puts("Impossible");34                 return 0;35             }36             mmp[i][j] = 1, dfs(i, j);37         }38     last = cnt;39     rep(i, 1, n) rep(j, 1, m) {40         if(s[i][j] == '?') s[i][j] = '#';41         else if(s[i][j] == '!') {42             s[i][j] = '#', cnt = 0;43             memset(mmp, 0, sizeof mmp);44             mmp[sx][sy] = 1, dfs(sx, sy);45             if(cnt + 1 == last) {46                 puts("Ambiguous");47                 return 0;48             }49             else s[i][j] = '.';50         }51     }52     rep(i, 1, n) puts(s[i] + 1);53     return 0;54 }