【Educational Codeforces Round20】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这场edu有点简单……

所以题目可能也有点奇奇怪怪的。

A.随意构造一下，可以发现只有当填满都不行时才可能无解。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[][];
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();k=read();
if(n*n<k){puts("-1");return ;}
for(int i=;i<=n&&k;i++){
a[i][i]=;
if(k==)break;
k--;
for(int j=i+;j<=n&&k>;j++)a[i][j]=a[j][i]=,k-=;
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)printf("%d ",a[i][j]);
puts("");
}
}

B.扫一遍就行了……

#include<bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> b;
int a[N];int n,now=;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();
for(int i=;i<=n;i++){
a[i]=read();if(a[i]==)b.push_back(i);
}
for(int i=;i<=n;i++){
if(now+<b.size()&&abs(b[now]-i)>abs(b[now+]-i))++now;
printf("%d ",abs(i-b[now]));
}
}

C.当时想出了倍数构造，但是有一点死活过不去……
加了个极大值特判过了……

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,ans=,m;
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
m=n/(k*(k+)/);
if(!m||k>){puts("-1");return ;}
for(ll j=;j*j<=n;j++){
if(n%j==){
if(j<=m&&j>ans)ans=j;if(n/j<=m&&(n/j)>ans)ans=n/j;
}
}
for(int i=;i<k;i++)cout<<i*ans<<' ';
n-=ans*(k-)*k/;
cout<<n<<endl;
}

D.答案显然可以二分。那么二分判断下是否可行就行。

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m,k,a[N];
char s[N];
inline bool check(int x){
int lx=,ans=;
for(int i=;i<=m;i++)if(a[i]-a[lx]>x)lx=i-,++ans;
return ans>k;
}
int main(){
int maxl=;
scanf("%d\n",&k);gets(s+);n=strlen(s+);s[n]=' ';
for(int i=;i<=n;i++){
if(s[i]=='-'||s[i]==' '){a[++m]=i;maxl=max(maxl,i-a[m-]);}
}
int l=maxl,r=n;
while(l<=r){
int mid=(l+r)>>;
if(check(mid))l=mid+;
else r=mid-;
}
printf("%d\n",l);
}

E.题解给了个带log的dp，被我记忆化水过去了……

#include<bits/stdc++.h>
using namespace std;
long long n,k;string s;
bool dp[][];
bool dfs(int u,int v){
if(u==n&&abs(v)==k)return ;
if(u==n||abs(v)>=k)return ;
if(dp[u][v])return ;
dp[u][v]=;
if(s[u]=='W')return dfs(u+,v+);
if(s[u]=='D')return dfs(u+,v);
if(s[u]=='L')return dfs(u+,v-);
if(dfs(u+,v+)){s[u]='W';return ;}
if(dfs(u+,v)){s[u]='D';return ;}
if(dfs(u+,v-)){s[u]='L';return ;}
return ;
}
int main(){
cin>>n>>k;cin>>s;
if(!dfs(,))puts("NO");
else cout<<s<<endl;
}

F.按照题解的式子推一样的，具体看官方题解吧。

#include<bits/stdc++.h>
#define N 1000005
#define yql 1000000007
using namespace std;
const int lim=1e5+;
int n,cnt[N],a[N],ans[N],p[N];
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
p[]=;for(int i=;i<=lim;i++)p[i]=(p[i-]<<)%yql;
n=read();
for(int i=;i<=n;i++)a[read()]++;
for(int i=;i<=lim;i++)for(int j=i+i;j<=lim;j+=i)a[i]+=a[j];
for(int i=lim;i;i--){
ans[i]=p[a[i]]-;
for(int j=i+i;j<=lim;j+=i){
ans[i]-=ans[j];
if(ans[i]<)ans[i]+=yql;
}
}
printf("%d\n",ans[]);
}

G.用动态开点线段树维护ST表（辣鸡cf怎么这么喜欢动态开点）

有点问题留坑待补。

#include<bits/stdc++.h>
#define N 100005
#define M 10000005
#define inf 2147483640
using namespace std;
int n,m,q,a[N],st[][N],lg[N];
int tagv[M],val[M],ls[M],rs[M],cnt=,mn=2e9;
inline int rmq(int l,int r){
int len=r-l+,t=lg[len];
return min(st[t][l],st[t][(r-<<t)+]);
}
inline int query(int l,int r){
int len=r-l+;if(len>=n)return mn;
if((l-)/n==(r-)/n)return rmq((l-)%n+,(r-)%n+);
else return min(rmq((l-)%n+,n),rmq(,(r-)%n+));
}
inline void pushup(int o,int l,int r){
if(~tagv[o])val[o]=tagv[o]?tagv[o]:query(l,r);
else val[o]=min(val[ls[o]],val[rs[o]]);
}
inline void pushdown(int o,int l,int r){
if(!ls[o])ls[o]=++cnt;if(!rs[o])rs[o]=++cnt;
if(~tagv[o]){
int mid=(l+r)>>;
tagv[ls[o]]=tagv[o];pushup(ls[o],l,mid);
tagv[rs[o]]=tagv[o];pushup(rs[o],mid+,r);
}
}
void change(int o,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){tagv[o]=v;return;}
int mid=(l+r)>>;pushdown(o,l,r);tagv[o]=-;
if(ql<=mid)change(ls[o],l,mid,ql,qr,v);
if(qr>mid)change(rs[o],mid+,r,ql,qr,v);
pushup(o,l,r);
}
int query(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return val[o];
int mid=(l+r)>>;pushdown(o,l,r);
int ans=inf;
if(ql<=mid)ans=min(ans,query(ls[o],l,mid,ql,qr));
if(qr>mid)ans=min(ans,query(rs[o],mid+,r,ql,qr));
return ans;
}
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
inline void initrmq(){
for(int j=;j<;++j)for(int i=;i<=n;++i)
if(i+(<<j)-<=n)st[j][i]=min(st[j-][i],st[j-][i+(<<j-)]);
}
int main(){
n=read();m=read();
for(int i=;i<=n;i++){
a[i]=read();mn=min(mn,a[i]);st[][i]=a[i];
}
for(int i=;i<=n;++i)lg[i]=lg[i>>]+;
initrmq();
q=read();pushup(,,n*m);
while(q--){
int opt=read(),l=read(),r=read();
if(opt==){
int v=read();change(,,n*m,l,r,v);
}
else printf("%d\n",query(,,n*m,l,r)); }
return ;
}