NOIP2017金秋冲刺训练营杯联赛模拟大奖赛第一轮Day2题解
上星期打的...题有点水，好多人都AK了
T1排个序贪心就好了
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int e,s;}a[maxn]; int n,m,s,k,x,y,cnt; int cp[maxn]; ll ans; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline bool cmp(poi a,poi b){return a.e==b.e?a.s>b.s:a.e<b.e;} inline bool cmp2(poi a,poi b){return a.s>b.s;} int main() { freopen("express.in","r",stdin); freopen("express.out","w",stdout); read(n);read(m);read(s);read(k); for(int i=1;i<=m;i++) { read(x);read(y); if(y<=2)continue; a[++cnt].e=x;a[cnt].s=y-2; } sort(a+1,a+1+cnt,cmp); for(int i=1;i<=cnt;i++)if(a[i].e!=a[i-1].e)cp[a[i].e]=i; for(int i=1;i<=n;i++) { if(!cp[i])return puts("-23333333"),0; int kk=k; for(int j=cp[i];j<=cnt&&a[j].e==i;j++) if(kk>0) { if(!s)return puts("-23333333"),0; s--;kk-=a[j].s;ans+=a[j].s;a[j].s=0; } if(kk>0)return puts("-23333333"),0; } if(s) { sort(a+1,a+1+cnt,cmp2); for(int i=1;i<=s;i++) ans+=a[i].s; } printf("%lld ",ans); return 0; }
T2我写的方法就太鶸了，所以只说某个很妙的做法（%%%腾腾太强辣！）
用一个指针扫，扫到某个括号就跳到对应的括号然后反向，遇到字符输出，模拟一下就知道是非常正确的
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010,inf=1e9; char s[maxn]; int n,top; int st[maxn],op[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { freopen("unknown.in","r",stdin); freopen("unknown.out","w",stdout); scanf("%s",s+1);n=strlen(s+1); for(int i=1;i<=n;i++) { if(s[i]=='(')st[++top]=i; if(s[i]==')')op[i]=st[top],op[st[top--]]=i; } for(int i=1,st=1;i<=n;i+=st) if(s[i]=='('||s[i]==')')i=op[i],st=-st; else printf("%c",s[i]); return 0; }