CF786 我不會告訴你鏈接在圖片里 CF786A CF786A題意 給出一個大小為 \(n\) 的環,點順時針從 \(1\to n\) 編號,兩個人(設為 \(0,1\))輪流移動其中的一個棋子。 對於第 \(opt\) 人,他能夠將這個棋子順時針移動 \(x\in S_{opt}\)(\(S_{ ...
CF786
CF786A
CF786A題意
給出一個大小為 \(n\) 的環,點順時針從 \(1\to n\) 編號,兩個人(設為 \(0,1\))輪流移動其中的一個棋子。
對於第 \(opt\) 人,他能夠將這個棋子順時針移動 \(x\in S_{opt}\)(\(S_{opt}\) 是提前給出的)個步數,當某個人將棋子挪到 \(1\) 時這個人獲勝。
問對於每一個位置和先手,要求你判斷先手必勝,後手必勝還是死迴圈。
\(n\le 7000\)
CF786A題解
首先我們知道,博弈論有一個性質,就是對於一種狀態 \(sta\),如果它所有能到達的狀態都是必勝,那麼這個狀態必敗,否則必勝。
首先我們知道 \(1\) 位置必敗,於是就可以嘗試倒著推情況。
記搜即可。
CF786A代碼
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 7100;
bool ans[maxn][2], vis[maxn][2];
int cnt[maxn][2];
int n;
vector<int> s[2];
void dfs(int u,int opt){
// printf("%d %d\n",u,opt);
if(vis[u][opt])return; vis[u][opt] = 1;
for(int i : s[opt ^ 1]){
int to = (u - i + n - 1) % n + 1;
// printf("%d %d %d\n",u,to,i);
if(to != 1){
if(!ans[u][opt]){
ans[to][opt ^ 1] = 1;
dfs(to,opt ^ 1);
}
else if((++cnt[to][opt ^ 1]) == s[opt ^ 1].size()){
ans[to][opt ^ 1] = 0;
dfs(to,opt ^ 1);
}
}
}
}
signed main(){
n = read();
for(int j = 0;j <= 1;j++)for(int i = read();i;i--)s[j].push_back(read());
dfs(1, 0);dfs(1, 1);
for(int i = 0;i <= 1;i++){
for(int j = 2;j <= n;j++){
printf(vis[j][i] ? (ans[j][i] ? "Win" : "Lose") : "Loop");
putchar(' ');
}
puts("");
}
return 0;
}
CF786B
CF786B題意
有 \(n\) 個點,現在有三種連邊(開傳送門)方式:
- \(1\space u\space v\space w\):將 \(u\to v\),這條邊邊權是 \(w\)。
- \(2\space u\space l\space r\space w\):對 \(i\in[l,r]\),將 \(u\to i\),邊權是 \(w\)。
- \(3\space u\space l\space r\space w\):對 \(i\in[l,r]\),將 \(i\to u\),邊權是 \(w\)。
求從 \(S\) 出發的單源最短路。
CF786B題解
線段樹優化建邊。
建兩棵樹,一棵自上而下的連邊,一棵自下而上建邊(分別設為 \(0,1\))。
然後對於 \(1,2\)(\(1\space u\space v\space w\) 可以看做 \(2\space u\space v\space v\space w\)),將 \(1\) 樹的 \([u,u]\) 連向 \(0\) 樹的 \([l,r]\) 節點。
而對於 \(3\),將 \(0\) 樹的 \([l,r]\) 連向 \(1\) 樹的 \([u,u]\)。
發現這樣連邊數量不會超過 \(\log n\) 條。
然後跑Dijsktra
就好了。
註意空間開大點。
CF786B代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, S;
int head[maxn << 2], tot;
struct edge{
int to, nexte;ll wei;
edge(int to = 0,int ne = 0,ll we = 0):to(to),nexte(ne),wei(we){}
}e[maxn << 5];
void add(int u,int v,ll w){e[++tot] = edge(v,head[u],w);head[u] = tot;}
int id[maxn << 2][2],cntpoint;
int rev[maxn];
struct Segment_Tree{
void build(int l,int r,int p,bool opt){
id[p][opt] = ++cntpoint; if(l == r){rev[l] = p;return;}
int mid = l + r >> 1;
build(l,mid,p << 1,opt);build(mid + 1,r,p << 1 | 1,opt);
if(opt == 0){add(id[p][opt],id[p << 1][opt],0);add(id[p][opt],id[p << 1 | 1][opt], 0);}
else{add(id[p << 1][opt],id[p][opt],0);add(id[p << 1 | 1][opt],id[p][opt],0);}
}
void query(int l,int r,int s,int t,int p,int u,ll wei,bool opt){
if(s <= l && r <= t){
if(opt == 0)add(id[rev[u]][opt ^ 1],id[p][opt],wei);
else add(id[p][opt],id[rev[u]][opt ^ 1],wei);
return;
}
int mid = l + r >> 1;
if(s <= mid)query(l,mid,s,t,p << 1,u,wei,opt);
if(mid < t)query(mid + 1,r,s,t,p << 1 | 1,u,wei,opt);
}
void query(int l,int r,int u,ll wei,bool opt){query(1,n,l,r,1,u,wei,opt);}
void DEBUG(bool opt = 0,int l = 1,int r = n,int p = 1){
printf("l = %d r = %d p = %d,opt = %d,id = %d\n",l,r,p,opt,id[p][opt]);
if(l == r)return;
int mid = l + r >> 1;
DEBUG(opt,l,mid,p << 1);DEBUG(opt,mid + 1,r,p << 1 | 1);
}
}tree[2];
typedef pair<ll,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > que;
ll dis[maxn << 2];bool book[maxn << 2];
signed main(){
n = read(); m = read(); S = read();int opt, l, r, u, w;
tree[0].build(1,n,1,0); tree[1].build(1,n,1,1);
// tree[0].DEBUG(0);tree[1].DEBUG(1);
for(int i = 1;i <= n;i++){
add(id[rev[i]][0],id[rev[i]][1],0);
add(id[rev[i]][1],id[rev[i]][0],0);
}
for(int i = 1;i <= m;i++){
opt = read();
if(opt == 1){
l = read(); r = read(); w = read();
tree[0].query(r,r,l,w,0);
}
else{
u = read(); l = read(); r = read();w = read();
tree[opt - 2].query(l, r, u, w, opt - 2);
}
}
// for(int u = 1;u <= cntpoint;u++){
// for(int i = head[u];i;i = e[i].nexte){
// printf("%d -> %d, w = %lld\n",u,e[i].to,e[i].wei);
// }
// }
memset(dis,0x3f,sizeof(dis));
dis[id[rev[S]][0]] = 0;que.push(make_pair(0,id[rev[S]][0]));
while(!que.empty()){
int u = que.top().second;que.pop();
if(book[u])continue;book[u] = 1;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to, w = e[i].wei;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
que.push(make_pair(dis[v],v));
}
}
}
for(int i = 1;i <= n;i++){
if(dis[id[rev[i]][0]] == INF)dis[id[rev[i]][0]] = -1;
printf("%lld ",dis[id[rev[i]][0]]);
}
return 0;
}
CF786C
CF786C題意
給出一個長度為 \(n\) 的數列 \(a\),要你對每個 \(k\in[1,n]\),給出最小的 \(m\),使得存在一種方案,將數列 \(a\) 劃分成 \(m\) 段,使得所有段不同的數字不超過 \(k\)。
\(n\le10^5\)
CF786C題解
這裡給出一個非常暴力的做法。
首先我們可以 \(O(n)\) 的計算出對於一個數字 \(k\) 的答案 \(f(k)\)。
觀察這個 \(f(k)\),不難發現這個函數滿足性質:
- \(f(k)\) 單調不增,且有連續的段。(顯然)
- \(f(k)\) 的取值不超過 \(\sqrt{n}\) 個。(不妨取一種極端情況,即 \(a\) 是 \(n\) 的一個排列,手玩一下就會發現這個極端情況也只有最多 \(\sqrt{n}\) 個取值)
於是就可以快樂的根號分治:
- 當 \(1\le k\le\sqrt{n}\) 時,直接算即可。
- 當 \(\sqrt{n}<k\) 時,二分找到與這個答案相等的最右端,然後這一段的答案都是這個。
如果害怕一個 \(k\) 的答案被重覆計算,那就類似記搜記錄下答案。
最大的點跑了 \(1044ms\),時限 \(2s\) 完全不慌。
時間複雜度也許是 \(O(n\sqrt{n}\log n)\) 的?但是完全跑不滿。
CF786C代碼
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int a[maxn], n;
int book[maxn];
int ans[maxn];
int solve(int k){
if(ans[k])return ans[k];
memset(book,0,sizeof(book));
int l = 0, cnt = 0, m = 0;
for(int i = 1;i <= n;i++){
cnt += !book[a[i]]++;
if(cnt > k){
for(int j = l + 1;j < i;j++)book[a[j]]--;
m++; cnt = 1; l = i - 1;
}
}
return ans[k] = m + (cnt ? 1 : 0);
}
signed main(){
n = read();for(int i = 1;i <= n;i++)a[i] = read();
for(int k = 1, len = sqrt(n);k <= n;k++){
if(k <= len){printf("%d ",solve(k));}
else{
int res = solve(k);
int l = k, r = n;
while(l <= r){
int mid = l + r >> 1;
if(solve(mid) == res){l = mid + 1;}
else r = mid - 1;
}
l--;
for(int j = k;j <= l;j++)printf("%d ",res);
k = l;
}
}
puts("");
return 0;
}
CF786D
*3400
不會
CF786E
CF786E題意
給你一棵有 \(n\) 個節點的樹和 \(m\) 個居民,每條邊上有一個守衛 \(i\) 守衛連接 \(u_i-v_i\) 的這條邊,每個居民 \(j\) 會從節點 \(u_j\) 走到節點 \(v_j\)。
現在對每個居民做出要求,要不然這個居民經過的所有守衛都有一條狗,要不然給這個居民發一條狗。
問滿足所有要求需要發多少條狗給居民,多少條狗給守衛?要求給出構造。
\(n\le2\times10^4,m\le10^4\)
CF786E題解
究極毒瘤碼農題,5.63KB極致壓行代碼你值得擁有
老規矩,先想想在序列上怎麼做?
不難想到網路流。
設源點 \(S\) 和匯點 \(T\),設網路流中一條邊形如 \((u,v,cap)\) 表示有一條 \(u\to v\),容量為 \(cap\) 的邊。
對於每個居民 \(i\) 和他的要求 \(u_i,v_i\),連接 \(w\in [u_i,v_i],(u,w,INF)\)。
然後對於每個居民 \(i\),連接 \((S,i,1)\)。
對於每個守衛 \(i\),連接 \((i,T,1)\)。
然後跑最小割即可。
等等等等,你這麼連邊不就 \(O(n^2)\) 了嗎,這不T飛了?
好好好,那就線段樹優化建邊(為啥這套題這麼喜歡線段樹優化建邊啊)
那樹上的怎麼辦?樹鏈剖分就完了。
那怎麼構造答案吶?
從源點 \(S\) 出發,每次走沒滿流的邊,走到一個守衛點時就說明至少存在一個居民在沒給狗狗的情況下包含了這個守衛,所以讓這個守衛拿一隻狗狗。
然後回頭看沒走到的居民點,說明這個居民被選擇了拿一隻狗狗,給一隻即可。
然後就沒了,只不過慢慢碼吧,我不會告訴你我碼了兩個半小時的。
CF786E代碼
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
vector<pair<int,int> > edg[maxn];
struct edge{
int to, nexte, cap, flow;
edge(int to = 0,int ne = 0,int ca = 0,int fl = 0):to(to),nexte(ne),cap(ca),flow(fl){}
}e[maxn << 3];
int head[maxn], tot = 1,S , T;
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u, v, cap);add(v, u, 0);}
int fa[maxn], siz[maxn], son[maxn],dep[maxn];
int edgid[maxn];//對每條邊,存儲在dep大的點上
void dfs1(int u,int f){
fa[u] = f;dep[u] = dep[f] + 1;
siz[u] = 1;son[u] = 0;
for(auto i : edg[u]){
int v = i.first;
if(v != f){
dfs1(v, u); siz[u] += siz[v];
edgid[v] = i.second;
son[u] = siz[son[u]] > siz[v] ? son[u] : v;
}
}
}
int top[maxn], dfn[maxn], idx, rev[maxn];//top重鏈頂端,dfn編號,rev[dfn[u]] = u
void dfs2(int u,int t){
top[u] = t;dfn[u] = ++idx;rev[idx] = u;
if(!son[u])return; dfs2(son[u],t);
for(auto i : edg[u]){
int v = i.first;
if(v != son[u] && v != fa[u])
dfs2(v, v);
}
}
int id[maxn], cntpoint;
int rrev[maxn];//rrev[l]=p表示[l,r]線上段樹上編號
struct Segment_Tree{
int d[maxn];
void build(int l,int r,int p){
id[p] = ++cntpoint;
if(l == r){addd(id[p],T,1);rrev[l] = p;return;}
int mid = l + r >> 1;
build(l,mid,p << 1);build(mid + 1,r,p << 1 | 1);
addd(id[p],id[p << 1],INF);addd(id[p],id[p << 1 | 1],INF);
}
void query(int l,int r,int s,int t,int p,int u){//opt=0 == u->[s,t],cap=INF;opt=1 == [s,t]->T,cap=t-s
if(s <= l && r <= t){addd(u,id[p],INF);return;}
int mid = l + r >> 1;
if(s <= mid)query(l,mid,s,t,p << 1,u);
if(mid < t)query(mid + 1,r,s,t,p << 1 | 1,u);
}
void query(int s,int t,int u){query(1,n,s,t,1,u);}
void build1(int l = 1,int r = n,int p = 1){
if(l == r){
for(int i = head[id[p]];i;i = e[i].nexte)
if(e[i].to == T){d[p] = e[i].flow;break;}
return;
}
int mid = l + r >> 1;
build1(l,mid,p << 1);build1(mid + 1,r,p << 1 | 1);
d[p] = d[p << 1] + d[p << 1 | 1];
}
void DEBUG(int l = 1,int r = n,int p = 1){
printf("[%d,%d], p = %d, id = %d\n",l,r,p,id[p]);
if(l == r)return; int mid = l + r >> 1;
DEBUG(l,mid,p << 1);DEBUG(mid + 1,r,p << 1 | 1);
}
}tree;
void query(int u,int v,int to){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
tree.query(dfn[top[u]],dfn[u],to);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u, v);
if(u == v)return;
tree.query(dfn[son[u]],dfn[v],to);
}
int dis[maxn],cur[maxn];bool book[maxn];
queue<int> que;
bool bfs(int S,int T){
while(!que.empty())que.pop();
for(int i = 0;i <= cntpoint;i++){dis[i] = INF;cur[i] = book[i] = 0;}
dis[S] = 0;que.push(S);cur[S] = head[S];book[S] = 1;
while(!que.empty()){
int u = que.front();que.pop();book[u] = 0;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to;
if(dis[v] == INF && e[i].cap > e[i].flow){
cur[v] = head[v];dis[v] = dis[u] + 1;
if(!book[v]){que.push(v);book[v] = 1;}
}
}
}
return dis[T] != INF;
}
int dfs(int u,int flow,int T){
if(!flow || u == T)return flow;
int res = 0;
for(int i = cur[u];i;i = e[i].nexte){
int v = e[i].to;cur[u] = i;
if(dis[v] == dis[u] + 1 && e[i].cap > e[i].flow){
int tmp = dfs(v, min(flow,e[i].cap - e[i].flow),T);
if(!tmp)dis[v] = INF;
e[i].flow += tmp;e[i ^ 1].flow -= tmp;
res += tmp;flow -= tmp;
}
}
return res;
}
int Dinic(int S,int T){
int mxflow = 0;
while(bfs(S,T))mxflow += dfs(S,INF,T);
return mxflow;
}
vector<int> citizen, guard;
bool vis[maxn];
void dfs3(int u,int f){
if(vis[u])return;vis[u] = 1;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to;
if(e[i].cap > e[i].flow)
dfs3(v, u);
}
}
signed main(){
n = read(); m = read();int u, v;cntpoint = m;
for(int i = 1;i < n;i++){
u = read(); v = read();
edg[u].push_back(make_pair(v, i));
edg[v].push_back(make_pair(u, i));
}
S = ++cntpoint;T = ++cntpoint;
dfs1(1, 0);dfs2(1, 1);tree.build(1,n,1);
for(int i = 1;i <= m;i++){
u = read(); v = read();
addd(S, i, 1); query(u, v, i);
}
int ans = Dinic(S,T);dfs3(S,S);
for(int i = 1;i <= m;i++)
if(!vis[i])citizen.push_back(i);
for(int i = 2;i <= n;i++)
if(vis[id[rrev[dfn[i]]]])guard.push_back(i);
printf("%d\n",citizen.size() + guard.size());
printf("%d",citizen.size());for(int i : citizen)printf(" %d",i);puts("");
printf("%d",guard.size());for(int i : guard)printf(" %d",edgid[i]);puts("");
// tree.DEBUG(); printf("ans = %d\n",ans);
// for(int u = 1;u <= cntpoint;u++)
// for(int i = head[u];i;i = e[i].nexte)
// printf("%d -> %d, cap = %d, flow = %d\n",u,e[i].to,e[i].cap,e[i].flow);
// for(int i = 1;i <= n;i++)
// printf("i=%d,fa=%d,siz=%d,son=%d,dep=%d,top=%d,dfn=%d,edgid=%d\n",i,fa[i],siz[i],son[i],dep[i],top[i],dfn[i],edgid[i]);
return 0;
}