E. MEX and Increments
F. Let’s Play the Hat?
G. Unusual Minesweeper
H. Permutation and Queries

?用個優(yōu)先隊列模擬。

map<int,int>ma; priority_queue<int> q;int main() {int t;scanf("%d", &t);while(t --){int n;scanf("%d", &n);while(q.size())q.pop(); ma.clear();q.push(-1); // 初始不用特判，好像也沒啥用 for(int i = 1;i <= n;i ++){int x;scanf("%d", &x);ma[x] ++;}LL ans = 0;for(int i = 0;i <= n;i ++){if(!q.size() || ans == -1) {ans = -1, cout<<ans<<' ';continue;}else ans += i-1-q.top(), cout<<ans+ma[i]<<' ', q.pop(); // ans +的是 成為i-1，再加i的個數(shù) while(ma[i]) q.push(i), ma[i]--; // 加入隊列。 }puts(""); }return 0; }

?直接模擬

int now = 0, n;void dp(int a, int b) // 產(chǎn)生 a 個 b人 的 桌子 {for(int i = 1;i <= a;puts(""), i ++){printf("%d", b);for(int i = 1;i <= b;now = (now+1)%n, i ++)printf(" %d", now+1);}return ; } int main() {int t;scanf("%d", &t);while(t --){int m, k;scanf("%d%d%d", &n, &m, &k);int x = m-n%m, y = n/m; // x 是下取整的桌子樹 int a = n%m, b = (n+m-1)/m; // a 是上取整的桌子數(shù) now = 0;while(k --){int t;dp(a, b); t = now;dp(x, y); now = t; // 下一次游戲接著 上一次游戲的最后一個的下一個擺 }}return 0; }

?并查集合并 + 貪心，寫的有點復雜

const int N = 3e5 + 10, mod = 998244353;struct P{int x, y, id;bool operator < (const P& b)const{return x == b.x ? y < b.y : x < b.x;} }; P a[N]; int fa[N], time[N]; int find(int u){return fa[u] == u ? u : fa[u] = find(fa[u]);} void merge(int u, int v){fa[find(u)] = find(v);}int main() {int t;scanf("%d", &t);for(int _ = 1;_ <= t;_ ++){int n, k;scanf("%d%d", &n, &k);for(int i = 1;i <= n;i ++){scanf("%d%d%d", &a[i].x, &a[i].y, time+i);a[i].id = i; fa[i] = i;}sort(a+1, a+n+1);for(int i = 1;i < n;i ++) // 按照x合并 {if(a[i].x == a[i+1].x && a[i+1].y <= a[i].y+k) merge(a[i].id, a[i+1].id);swap(a[i].x, a[i].y);}swap(a[n].x, a[n].y); // 這步在上面最后一次沒到 n 需要加上。 sort(a+1, a+n+1);for(int i = 1;i < n;i ++) // 按照y合并 if(a[i].x == a[i+1].x && a[i+1].y <= a[i].y+k) merge(a[i].id, a[i+1].id);for(int i = 1, t;i <= n;i ++)if((t = find(i)) != i)time[t] = min(time[t], time[i]), time[i] = -1; // = -1代表不需要考慮 sort(time+1, time+n+1);int ans = -1, pos = n;while(pos)if(time[pos--] > ans) ans++;else break;printf("%d\n", ans);}return 0; }

?原來分塊是這樣寫的啊，在鏈表上分塊，jump[i]代表i進行block次next得到的位置，然后查詢就是直接查詢，修改那就是先把x和y改了，然后還需要改一些數(shù)字的jump[]，這些數(shù)字就是x的前block個pre，y的前block的pre，好牛啊，臥槽。

int r[N], l[N], jump[N], block;void change(int x) {int to = x, i = block;while(i) to = r[to], i--;i = block;while(i) jump[x] = to, x = l[x], to = l[to], i --; }int main() {int n, q;scanf("%d%d", &n, &q);for(int i = 1;i <= n;i ++) scanf("%d", r+i), l[r[i]] = i;block = sqrt(n) + 1;for(int i = 1;i <= n;i ++){jump[i] = i;for(int j = 1;j <= block;j ++) jump[i] = r[jump[i]];}while(q --){int p, x, y;scanf("%d%d%d", &p, &x, &y);if(p == 1){swap(r[x], r[y]);l[r[x]] = x, l[r[y]] = y; // 先改 x, y change(x), change(y); // 再改 jump[] }else{while(y >= block) x = jump[x], y -= block;while(y) x = r[x], y --;printf("%d\n", x); }}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #762 (Div. 3)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。