codeforces有幾個div，Codeforces Round #429 Div. 1-基礎知識庫-匯編語言學習筆記

codeforces有幾個div，Codeforces Round #429 Div. 1

2023-12-06 阅读 24 评论 0

摘要：　　A：甚至連題面都不用仔細看，看一下樣例就知道是要把大的和小的配對了。 #include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #defin

　　A：甚至連題面都不用仔細看，看一下樣例就知道是要把大的和小的配對了。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,id[N],ans[N];
struct data
{int x,y,i;bool operator <(const data&a)  const{return y<a.y;}
}a[N];
bool cmp(const data&a,const data&b)
{return a.x>b.x;
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read();for (int i=1;i<=n;i++) a[i].x=read();for (int i=1;i<=n;i++) a[i].y=read(),a[i].i=i;sort(a+1,a+n+1);for (int i=1;i<=n;i++) id[i]=a[i].i;//��iС����id[i] sort(a+1,a+n+1,cmp);for (int i=1;i<=n;i++) ans[id[i]]=a[i].x;for (int i=1;i<=n;i++) printf("%d ",ans[i]);return 0;//NOTICE LONG LONG!!!!!
}

　　B：vp時拿命想都不會，結果一看sol發現idea還很大一部分是我自己造過的題，簡直自閉。顯然度數之和應該是偶數，先給不要求度數的隨便分配一下滿足要求。然后找一棵生成樹，自底向上只選樹邊以滿足度數要求即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,m,a[N],p[N],ans[N],u,t;
bool flag[N];
struct data{int to,nxt;
}edge[N<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{flag[k]=1;for (int i=p[k];i;i=edge[i].nxt)if (!flag[edge[i].to]){dfs(edge[i].to);if (a[edge[i].to]) ans[++u]=(i-1)/2+1,a[k]^=1;}
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read(),m=read();int cnt=0,cnt2=0;for (int i=1;i<=n;i++) a[i]=read(),cnt+=(a[i]==-1),cnt2+=(a[i]==1);if (cnt==0&&(cnt2&1)) {cout<<-1;return 0;}for (int i=1;i<=n;i++) if (a[i]==-1) if (cnt2&1) cnt2=0,a[i]=1;else a[i]=0;for (int i=1;i<=m;i++){int x=read(),y=read();addedge(x,y),addedge(y,x);}dfs(1);cout<<u<<endl;for (int i=1;i<=u;i++) printf("%d ",ans[i]);return 0;//NOTICE LONG LONG!!!!!
}

　　C：我省去年初中組直接把這個題搬過來壓軸，很久以前口胡過然而并沒有寫，于是vp時就去搬了份代碼交了（）。

　　顯然可以先把每個數的平方因子去掉。然后即相當于要求相鄰兩數存在不同的質因子。也就相當于要求相鄰兩數不同。于是把所有數排個序，從小到大考慮每種數，設f[i][j][k]為前i個數當前有j對相同數相鄰且其中有k對和當前數相同，轉移顯然。

　　D：顯然滿足條件的數一定是區間內出現次數前k大的。考慮回滾莫隊，維護一下出現次數區間前5大的數即可。稍微卡卡常就行了。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
#define N 300010
#define ll long long
int n,m,a[N],b[N],cnt[N],mx[6],ans[N],tmp_mx[6];
struct data
{int x,y,k,i,u;bool operator <(const data&a) const{return k<a.k||k==a.k&&y<a.y;}
}q[N];
void ins(int qwq)
{if (cnt[qwq]<cnt[mx[5]]) return;int p=0;for (int k=1;k<=5;k++) if (mx[k]==qwq) {p=k;break;}if (!p) mx[5]=qwq,p=5;while (p>1&&cnt[mx[p]]>cnt[mx[p-1]]) swap(mx[p],mx[p-1]),p--;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("b.in","r",stdin);freopen("b.out","w",stdout);const char LL[]="%I64d\n";
#elseconst char LL[]="%lld\n";
#endifn=read(),m=read();for (int i=1;i<=n;i++) a[i]=read();int block=sqrt(n);for (int i=1;i<=m;i++) q[i].x=read(),q[i].y=read(),q[i].u=read(),q[i].k=q[i].x/block,q[i].i=i;sort(q+1,q+m+1);for (int i=1;i<=m;i++){for (int k=1;k<=5;k++) mx[k]=0;int t=i;while (t<m&&q[t+1].k==q[i].k) t++;while (i<=t&&q[i].y<(q[i].k+1)*block){for (int j=q[i].x;j<=q[i].y;j++){cnt[a[j]]++;ins(a[j]);}ans[q[i].i]=N;for (int k=1;k<=5;k++) if (1ll*cnt[mx[k]]*q[i].u>q[i].y-q[i].x+1) ans[q[i].i]=min(ans[q[i].i],mx[k]);if (ans[q[i].i]==N) ans[q[i].i]=-1;for (int j=q[i].x;j<=q[i].y;j++) cnt[a[j]]--;i++;for (int k=1;k<=5;k++) mx[k]=0;}int r=(q[i].k+1)*block-1;for (int j=i;j<=t;j++){while (r<q[j].y){cnt[a[++r]]++;ins(a[r]);}for (int k=1;k<=5;k++) tmp_mx[k]=mx[k];for (int k=(q[i].k+1)*block-1;k>=q[j].x;k--){cnt[a[k]]++;ins(a[k]);}ans[q[j].i]=N;for (int k=1;k<=5;k++) if (1ll*cnt[mx[k]]*q[j].u>q[j].y-q[j].x+1) ans[q[j].i]=min(ans[q[j].i],mx[k]);if (ans[q[j].i]==N) ans[q[j].i]=-1;for (int k=(q[i].k+1)*block-1;k>=q[j].x;k--) cnt[a[k]]--;for (int k=1;k<=5;k++) mx[k]=tmp_mx[k];}r=(q[i].k+1)*block-1;for (int j=i;j<=t;j++)while (r<q[j].y) cnt[a[++r]]=0;i=t;}for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}

　　事實上直接拿棵主席樹在上面暴力查詢復雜度大約就是O(knlogn)。具體并不會證。感覺很對就行了。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,m,root[N],a[N],cnt;
struct data{int l,r,x;
}tree[N<<5];
void ins(int &k,int l,int r,int x)
{tree[++cnt]=tree[k];k=cnt;tree[k].x++;if (l==r) return;int mid=l+r>>1;if (x<=mid) ins(tree[k].l,l,mid,x);else ins(tree[k].r,mid+1,r,x);
}
int query(int x,int y,int l,int r,int u)
{if (tree[y].x-tree[x].x<=u) return -1;if (l==r) return l;int mid=l+r>>1;int v=query(tree[x].l,tree[y].l,l,mid,u);if (v==-1) return query(tree[x].r,tree[y].r,mid+1,r,u);else return v;
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read(),m=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++){root[i]=root[i-1];ins(root[i],1,n,a[i]);}for (int i=1;i<=m;i++){int l=read(),r=read(),x=read();printf("%d\n",query(root[l-1],root[r],1,n,(r-l+1)/x));}return 0;//NOTICE LONG LONG!!!!!
}

　　E：因為用來異或的dist隨祖先深度減小連續遞增，考慮一個套路的對位運算的分塊，即固定高位的前一半數字，不妨設令其去掉后9位的部分相同。那么即對于每個點，考慮其向上2⁹個點作為一塊。對于每一塊，考慮以前一半數字建trie，葉子處存儲a_i^x的最大值，其中x是其與該塊下端點的深度差，因為深度差的后9位對于該塊每個點來說在所有需要用到該塊的查詢中都是一樣的。這樣預處理的復雜度是7*2⁹*n。考慮查詢，從查詢點往上暴跳考慮每個塊，如果塊不完整顯然暴力即可，否則先對前一半數字trie上按位貪心，貪完之后即可固定答案中點i的a_i前一半數字，并且可以發現答案已經被預處理出來了。查詢復雜度q*(2⁹+n*7/2⁹)。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 50010
#define M 150010
#define BLOCK 512
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
int n,m,a[N],p[N],fa[N],fa512[N],deep[N],root[N],f[N][N/BLOCK+10],trie[N*256][2],t,cnt;
struct data{int to,nxt;
}edge[N<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void dfs(int k)
{for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=fa[k]){fa[edge[i].to]=k;deep[edge[i].to]=deep[k]+1;dfs(edge[i].to);}
}
void ins(int &k,int x)
{if (!k) k=++cnt;for (int i=k,j=6;j>=0;j--){if (!trie[i][(x&(1<<j))>0]) trie[i][(x&(1<<j))>0]=++cnt;i=trie[i][(x&(1<<j))>0];}
}
signed main()
{
#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);
#endifn=read(),m=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<n;i++){int x=read(),y=read();addedge(x,y),addedge(y,x);}dfs(1);for (int i=1;i<=n;i++)if (deep[i]>=BLOCK){fa512[i]=i;for (int j=0;j<BLOCK;j++){int x=fa512[i];ins(root[i],a[x]>>9);f[i][a[x]>>9]=max(f[i][a[x]>>9],a[x]^j);fa512[i]=fa[fa512[i]];}}for (int i=1;i<=m;i++){int y=read(),x=read(),u=x,v=0,ans=0;while (deep[u]-deep[y]>=BLOCK){int w=0;for (int k=root[u],j=6;j>=0;j--)if (v&(1<<j)){if (trie[k][0]) k=trie[k][0],w=w<<1;else k=trie[k][1],w=w<<1|1;}else{if (trie[k][1]) k=trie[k][1],w=w<<1|1;else k=trie[k][0],w=w<<1;}ans=max(ans,f[u][w]^(v<<9));u=fa512[u];v++;}while (u!=y) ans=max(ans,a[u]^deep[x]-deep[u]),u=fa[u];ans=max(ans,a[y]^deep[x]-deep[y]);printf("%d\n",ans);}return 0;//NOTICE LONG LONG!!!!!
}

轉載于:https://www.cnblogs.com/Gloid/p/10503993.html

原文链接：https://hbdhgg.com/5/190673.html

发表评论: