http://codeforces.com/contest/940
A水题
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;int a[N]; int main() {int n,d;scanf("%d%d",&n,&d);for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int minn=100000;for(int i=0;i<n;i++){bool ok=0;for(int j=i;j<n;j++){if(a[j]-a[i]>d){ok=1; // printf("%d %d\n",i,j-1);minn=min(minn,n-(j-i));break;}}if(!ok){ // printf("%d+++\n",i);minn=min(minn,i);}}printf("%d\n",minn);return 0; } /****************************************/
B直接暴力，忘了考虑1 的情况t了一发
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;int main() {ll n,k,a,b,ans=0;scanf("%lld%lld%lld%lld",&n,&k,&a,&b);if(k==1){printf("%lld\n",(n-1)*a);return 0;}while(n){if(n<k){ans+=a*(n-1);break;}else{if(n%k==0){ans+=min((n-n/k)*a,b);n=n/k;}else{ans+=(n%k)*a;n-=n%k;}}}printf("%lld\n",ans);return 0; } /****************************************/
C从后往前扫找第一个个能替换的换了，然后把后面的全部换成最小,O(n*26)
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;char s[N]; int num[30]; int main() {int n,k;scanf("%d%d%s",&n,&k,s);for(int i=0;i<n;i++)num[s[i]-'a']=1;int f=0;for(int i=0;i<26;i++){if(num[i]){f=i;break;}}if(n<k){printf("%s",s);for(int i=0;i<k-n;i++)printf("%c",(char)(f+'a'));puts("");}else{for(int i=k-1;i>=0;i--){int ok=-1;for(int j=0;j<26;j++){if(num[j]&&s[i]-'a'<j){ // printf("%d %d\n",i,j);ok=j;break;}}if(ok!=-1){s[i]=(char)(ok+'a'); // printf("%d %c\n",i,s[i]);for(int j=i+1;j<k;j++)s[j]=(char)(f+'a');for(int j=0;j<k;j++)printf("%c",s[j]);break;}}}return 0; } /****************************************/
D枚举所有情况找l和r即可，见过最简单的d题= =
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;char s[N]; int a[N],b[N]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%s",s+1);for(int i=1;i<=n;i++){if(s[i]=='1')b[i]=1;else b[i]=0;}int l=-1e9,r=1e9;for(int i=5;i<=n;i++){if(!b[i]&&b[i-1]&&b[i-2]&&b[i-2]&&b[i-3]){r=min(r,a[i]-1);r=min(r,a[i-1]-1);r=min(r,a[i-2]-1);r=min(r,a[i-3]-1);r=min(r,a[i-4]-1);}else if(b[i]&&!b[i-1]&&!b[i-2]&&!b[i-2]&&!b[i-3]){l=max(l,a[i]+1);l=max(l,a[i-1]+1);l=max(l,a[i-2]+1);l=max(l,a[i-3]+1);l=max(l,a[i-4]+1);}}printf("%d %d\n",l,r);return 0; } /****************************************/
E，题意：把一堆数分成若干块，每个块的价值是去掉前k/c（k是块大小）小的数的和，求所有块最小的和
很明显每个块分尽可能的c个，然后每次可以用dp来算dp【i】=min（dp【i-1】+a【i】，dp【i-c】+sum（i-c，i））求sum复杂度是o(n)，可以用线段树预处理然后优化到o（logn），总复杂度O（nlogn）
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=100000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;ll mi[N<<2],sum[N<<2],a[N],dp[N]; void pushup(int rt) {mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) {if(l==r){mi[rt]=sum[rt]=a[l];return ;}int m=(l+r)>>1;build(ls);build(rs);pushup(rt); } ll querysum(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return sum[rt];int m=(l+r)>>1;ll ans=0;if(L<=m)ans+=querysum(L,R,ls);if(m<R)ans+=querysum(L,R,rs);return ans; } ll querymi(int L,int R,int l,int r,int rt) {if(L<=l&&r<=R)return mi[rt];int m=(l+r)>>1;ll ans=1e9+10;if(L<=m)ans=min(ans,querymi(L,R,ls));if(m<R)ans=min(ans,querymi(L,R,rs));return ans; } int main() {int n,c;scanf("%d%d",&n,&c);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,n,1);for(int i=1;i<=n;i++){dp[i]=dp[i-1]+a[i];if(i-c>=0){ll all=querysum(i-c+1,i,1,n,1);dp[i]=min(dp[i],dp[i-c]+all-querymi(i-c+1,i,1,n,1));}}printf("%lld\n",dp[n]);return 0; } /****************************************/
F，题意：一些数，两个操作1，把某个位置的数改成另一个，2，查询mex（数的总和个数）
带修莫队裸题，先把数离散化，然后暴力跑莫队即可，维护一个数的个数，一个数的个数有多少个，注意块一定要开n^(2/3)个,sqrt(n)会t，复杂度O（n^(5/3)+nlogn）
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0)using namespace std;const double g=10.0,eps=1e-12; const int N=300000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;int a[N],belong[N],ans[N],now[N]; int l=1,r=0,num[N],t,co[N]; int Hash[N]; struct que{int l,r,tim,id; }qu[N]; struct change{int pos,suf,pre; }ch[N]; bool cmp(que a,que b) {if(belong[a.l]==belong[b.l]){if(belong[a.r]==belong[b.r])return a.tim<b.tim;else return a.r<b.r;}else return a.l<b.l; } void gao(int x,int d) {if(d==1){num[co[x]]--;co[x]++;num[co[x]]++;}else{num[co[x]]--;co[x]--;num[co[x]]++;} } void go(int x,int d) {if(l<=x&&x<=r)gao(d,1),gao(a[x],-1);a[x]=d; } int main() {int n,q,cnt=0;scanf("%d%d",&n,&q);int block=3000;for(int i=1;i<=n;i++){scanf("%d",&a[i]);Hash[cnt++]=a[i];now[i]=a[i];belong[i]=(i-1)/block+1;}int cnt1=0,cnt2=0;for(int i=1;i<=q;i++){int op,a,b;scanf("%d%d%d",&op,&a,&b);if(op==1)qu[++cnt1]={a,b,cnt2,cnt1};else ch[++cnt2]={a,b,now[a]},now[a]=b,Hash[cnt++]=b;}sort(Hash,Hash+cnt);cnt=unique(Hash,Hash+cnt)-Hash;for(int i=1;i<=n;i++)a[i]=lower_bound(Hash,Hash+cnt,a[i])-Hash;for(int i=1;i<=cnt2;i++){ch[i].pre=lower_bound(Hash,Hash+cnt,ch[i].pre)-Hash;ch[i].suf=lower_bound(Hash,Hash+cnt,ch[i].suf)-Hash;} // for(int i=1;i<=cnt1;i++) // printf("%d %d %d %d\n",qu[i].l,qu[i].r,qu[i].id,qu[i].tim);sort(qu+1,qu+1+cnt1,cmp);for(int i=1;i<=cnt1;i++){while(t<qu[i].tim)go(ch[t+1].pos,ch[t+1].suf),t++;while(t>qu[i].tim)go(ch[t].pos,ch[t].pre),t--;while(l<qu[i].l)gao(a[l],-1),l++;while(l>qu[i].l)gao(a[l-1],1),l--;while(r<qu[i].r)gao(a[r+1],1),r++;while(r>qu[i].r)gao(a[r],-1),r--;int res=1;while(num[res])res++;ans[qu[i].id]=res;}for(int i=1;i<=cnt1;i++)printf("%d\n",ans[i]);return 0; } /****************************************/
