Codeforces Round #398 (Div. 2) 题解(待续)

2019-11-08 00:43:12

字体：大中小

来源：转载

供稿：网友

A Codeforces Round #398 (Div. 2)

#include<bits/stdc++.h>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define ForD(i,n) for(int i=n;i;i--)#define ForkD(i,k,n) for(int i=n;i>=k;i--)#define RepD(i,n) for(int i=n;i>=0;i--)#define Forp(x) for(int p=PRe[x];p;p=Next[p])#define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1)#define Rson ((o<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (1000000007)#define pb push_back#define mp make_pair #define fi first#define se second#define vi vector<int> #define pi pair<int,int>#define SI(a) ((a).size())#define Pr(kcase,ans) printf("Case #%d: %I64d/n",kcase,ans);#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;#define PRi2D(a,n,m) For(i,n) { / For(j,m-1) cout<<a[i][j]<<' ';/ cout<<a[i][m]<<endl; / } #pragma comment(linker, "/STACK:102400000,102400000")#define ALL(x) (x).begin(),(x).end()typedef long long ll;typedef long double ld;typedef unsigned long long ull;ll mul(ll a,ll b){return (a*b)%F;}ll add(ll a,ll b){return (a+b)%F;}ll sub(ll a,ll b){return ((a-b)%F+F)%F;}void upd(ll &a,ll b){a=(a%F+b%F)%F;}int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f;} #define MAXN (102345)int a[MAXN];int c[MAXN];priority_queue<int> q;int main(){// freopen("A.in","r",stdin);// freopen(".out","w",stdout); int n=read(); For(i,n) cin>>a[i],c[i]=a[i]; sort(c+1,c+1+n); int p=n; For(i,n) { q.push(a[i]); bool fl=0; while(!q.empty()&&q.top()==c[p]) { if (!fl) fl=1;else putchar(' '); cout<<c[p--]; q.pop(); } puts(""); } return 0;}

B The Queue

还有点小问题

C Garland

#include<bits/stdc++.h>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define ForD(i,n) for(int i=n;i;i--)#define ForkD(i,k,n) for(int i=n;i>=k;i--)#define RepD(i,n) for(int i=n;i>=0;i--)#define Forp(x) for(int p=Pre[x];p;p=Next[p])#define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1)#define Rson ((o<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (1000000007)#define pb push_back#define mp make_pair #define fi first#define se second#define vi vector<int> #define pi pair<int,int>#define SI(a) ((a).size())#define Pr(kcase,ans) printf("Case #%d: %I64d/n",kcase,ans);#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;#define PRi2D(a,n,m) For(i,n) { / For(j,m-1) cout<<a[i][j]<<' ';/ cout<<a[i][m]<<endl; / } #pragma comment(linker, "/STACK:102400000,102400000")#define ALL(x) (x).begin(),(x).end()typedef long long ll;typedef long double ld;typedef unsigned long long ull;ll mul(ll a,ll b){return (a*b)%F;}ll add(ll a,ll b){return (a+b)%F;}ll sub(ll a,ll b){return ((a-b)%F+F)%F;}void upd(ll &a,ll b){a=(a%F+b%F)%F;}int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f;} #define MAXN (1234567)vi edges[MAXN];int fa[MAXN],d[MAXN];int n,c[MAXN]={0},a[MAXN]={0},b[MAXN]={0};void dfs(int x,int dep=0) { Rep(i,SI(edges[x])) { int v=edges[x][i]; if (b[v]) continue; dfs(v,dep+1); a[x]+=a[v]; } a[x]+=c[x]; d[x]=dep;}void dfs2(int x) { Rep(i,SI(edges[x])) { int v=edges[x][i]; dfs2(v); b[v]=1; } b[x]=1;}int main(){// freopen("C.in","r",stdin);// freopen(".out","w",stdout); cin>>n; int tt=0,ro; For(i,n) { fa[i]=read(); if (!fa[i]) ro=i; int t=read(); edges[fa[i]].pb(i); c[i]=t;tt+=t; } if (tt%3!=0) { puts("-1");return 0; } tt/=3; MEM(a) dfs(ro); int ans1=0,dp=-1; For(i,n) if (a[i]==tt&&i!=ro && dp<=d[i]) ans1=i,dp=d[i]; if (!ans1) { puts("-1");return 0; } dfs2(ans1); MEM(a) b[ans1]=1; dfs(ro); int ans2=0; dp=-1; For(i,n) if (!b[i] && a[i]==tt&&i!=ro && dp<=d[i]) ans2=i,dp=d[i]; if (!ans2) { puts("-1");return 0; } if (ans1>ans2) swap(ans1,ans2); cout<<ans1<<' '<<ans2<<endl; return 0;}

D Cartons of milk

二分

#include<bits/stdc++.h>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define ForD(i,n) for(int i=n;i;i--)#define ForkD(i,k,n) for(int i=n;i>=k;i--)#define RepD(i,n) for(int i=n;i>=0;i--)#define Forp(x) for(int p=Pre[x];p;p=Next[p])#define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1)#define Rson ((o<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (1000000007)#define pb push_back#define mp make_pair #define fi first#define se second#define vi vector<int> #define pi pair<int,int>#define SI(a) ((a).size())#define Pr(kcase,ans) printf("Case #%d: %I64d/n",kcase,ans);#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;#define PRi2D(a,n,m) For(i,n) { / For(j,m-1) cout<<a[i][j]<<' ';/ cout<<a[i][m]<<endl; / } #pragma comment(linker, "/STACK:102400000,102400000")#define ALL(x) (x).begin(),(x).end()typedef long long ll;typedef long double ld;typedef unsigned long long ull;ll mul(ll a,ll b){return (a*b)%F;}ll add(ll a,ll b){return (a+b)%F;}ll sub(ll a,ll b){return ((a-b)%F+F)%F;}void upd(ll &a,ll b){a=(a%F+b%F)%F;}int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f;} #define MAXN (2345678)ll a[MAXN];pair<ll,int > b[MAXN];ll c[MAXN];int n,m,k;ll calc(int p) { int l1=1,l2=m-p+1; int t=0; For(i,n+p) { if (l1>n) c[++t]=b[l2].fi,l2++; else if (l2>m) c[++t]=a[l1],l1++; else { if (a[l1]<b[l2].fi) c[++t]=a[l1],l1++; else c[++t]=b[l2].fi,l2++; } } sort(c+1,c+1+t); ll dt=0,nd=k; For(i,t) { if (!nd) ++dt,nd+=k; if (c[i]<dt) return 0; nd--; } return 1;}int main(){// freopen("D.in","r",stdin);// freopen(".out","w",stdout); n=read(),m=read(),k=read(); For(i,n) a[i]=read(); For(i,m) b[i]=mp(read(),i); sort(a+1,a+1+n); sort(b+1,b+1+m); int l=0,r=m,ans=0; if (!calc(0)) puts("-1"); else { while(l<=r) { int m=(l+r)/2; if (calc(m)) ans=m,l=m+1; else r=m-1; } cout<<ans<<endl; bool fl=0; Fork(i,m-ans+1,m) { if (!fl) fl=1; else putchar(' '); cout<<b[i].se; }puts(""); } return 0;}

上一篇：【技巧】SQL中修改列名（column）

下一篇：关于从SVN检出项目后，项目名称还是之前修改之前或者项目名称不对问题