612A - The Text Splitting 20171121
简单字符串处理题
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p,q;
string s;
void print(int _)
{
int k=_+(n-_*p)/q;
printf("%d\n",k);
for(int i=;i<_;i++)
{
for(int j=;j<p;j++)
printf("%c",s[i*p+j]);
printf("\n");
}
for(int i=_;i<k;i++)
{
for(int j=;j<q;j++)
printf("%c",s[_*p+(i-_)*q+j]);
printf("\n");
}
}
int main()
{
scanf("%d%d%d",&n,&p,&q);
cin>>s;
for(int i=;i*p<=n;i++)
if((n-i*p)%q==)
return print(i),;
return printf("-1\n"),;
}
612B - HDD is Outdated Technology 20171121
设\(p_{f_i}=i\)，则有\(ans=\sum_{i=2}^{n}|p_i-p_{i-1}|\)
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int n,f,p[];
LL ans;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&f),p[f]=i;
for(int i=;i<=n;i++)
ans+=1ll*abs(p[i]-p[i-]);
printf("%I64d\n",ans);
return ;
}
612C - Replace To Make Regular Bracket Sequence 20171121
根据题意扫一遍就好了
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ans;
string s;
stack<char>_;
bool check(char a,char b)
{
if(a=='<' && b=='>')return true;
if(a=='{' && b=='}')return true;
if(a=='[' && b==']')return true;
if(a=='(' && b==')')return true;
return false;
}
int main()
{
cin>>s;
for(int i=;i<s.size();i++)
{
if(s[i]=='<')_.push('<');
if(s[i]=='{')_.push('{');
if(s[i]=='[')_.push('[');
if(s[i]=='(')_.push('(');
if(s[i]=='>' || s[i]=='}' || s[i]==']' || s[i]==')')
if(!_.size())return printf("Impossible\n"),;
else ans+=!check(_.top(),s[i]),_.pop();
}
if(_.size())return printf("Impossible\n"),;
return printf("%d\n",ans),;
}
612D - The Union of k-Segments 20171121
将线段按左端点排序，通过优先队列（存储内容为线段的右端点）在每次访问一个线段时将已经无效的线段删去，获取仍有效的线段数即可
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct rua{int l,r;}a[];
priority_queue<int,vector<int>,greater<int> >q;
bool cmp(rua x,rua y){return x.l<y.l || (x.l==y.l && x.r>y.r);}
int n,k,ll,rr,INF=-;vector<int>ans[];
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a+,a+n+,cmp);rr=INF;
for(int i=;i<=n;i++)
{
while(q.size() && q.top()<a[i].l)q.pop();
if(q.size()<k)
{
if(rr!=INF)
ans[].push_back(ll),ans[].push_back(rr);
if(rr<a[i].l)rr=INF;
ll=a[i].l;
}
q.push(a[i].r);
while(q.size()>k)q.pop();
if(q.size()==k)rr=max(rr,q.top());
}
if(rr!=INF)ans[].push_back(ll),ans[].push_back(rr);
printf("%d\n",ans[].size());
for(int i=;i<ans[].size();i++)
printf("%d %d\n",ans[][i],ans[][i]);
return ;
}
612E - Square Root of Permutation 20180910
把\(q_i\)看做是从\(i\)向\(q_i\)连一条有向边，那么可以发现这是一个所有点的入度、出度均为1的有向图，显然这个图是由若干个不相交的环组成的。可以发现，\(p_i\)和\(i\)肯定在一个环内，所以对每个\(i\)，可以找出\(i\)所在循环节的大小。若循环节的大小\(sz\)为奇数，那么被遍历的所有点在原图就处于同一个大小为\(sz\)的环内。若\(sz\)为偶数，则需要另外一个大小同为\(sz\)的循环节与其组成大小为\(2\cdot sz\)的环，直接模拟即可。答案无解当且仅当存在偶数\(sz\)，使得长度为\(sz\)的循环节个数为奇数。
#include<bits/stdc++.h>
using namespace std;
#define N 1000001
int n,p[N],q[N],c[N],s[N];
bool vis[N];
void Union(int x,int y,int sz)
{
s[sz]=;
for(int i=;i<=sz;i++)
q[x]=y,q[y]=p[x],x=p[x],y=p[y];
}
void rua(int x,int sz)
{
if(sz%==)
if(s[sz]){Union(x,s[sz],sz);return;}
else{s[sz]=x;return;}
c[]=x;
for(int i=,cur=p[x];cur!=x;c[i++]=cur,cur=p[cur]);
for(int i=;i<sz;i++)
if(i*<sz-)q[c[i]]=c[i+(sz+)/];
else q[c[i]]=c[i-(sz-)/];
}
void dfs(int cur,int sz)
{
vis[cur]=true;
if(vis[p[cur]])rua(cur,sz);
else dfs(p[cur],sz+);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&p[i]);
for(int i=;i<=n;i++)
if(!vis[i])dfs(i,);
for(int i=;i<=n;i++)
if(s[i])return printf("-1\n"),;
for(int i=;i<=n;i++)
printf("%d%c",q[i],i<n?' ':'\n');
}
612F - Simba on the Circle 20180911
首先为了方便程序运行，先对a[i]进行离散化处理。
设f[i]表示当小于等于a[i]的数全部选完之后，还要走几步结束
g[i][j]表示当小于等于a[i]的数全部选完之后，选遍a[i]+1并最终走到j的步数，显然a[j]要满足a[j]=a[i]+1
然后设d[i]是满足a[j]=i的j的集合，这样就有f[j]=min{g[j][d[i+1][k]]+f[d[i+1][k]]}
问题就在于如何求g[i][j]
可以发现，最优的走法有两种，一种是先顺时针走到j的前一项值为a[j]的数，然后再逆时针走到j，另一种则是先逆时针走，再顺时针走到j，两者对应的答案取最小值就好了
思路大概就是这样，但是细节上有很多方面要处理，本弱就因为细节调了快一个小时_(:з」∠)_
#include<bits/stdc++.h>
using namespace std;
#define N 2001
int n,m,s,a[N],p[N],f[N],l[N][N],nxt[N],di[N][N],g[N][N],dis[N][N],vis[N];
vector<int>d[N];
int check1(int op,int ed,int x)
{
if(ed<op)ed+=n;
if(x<op)x+=n;
return x<ed?(x-)%n+:op;
}
int check2(int op,int ed,int x)
{
if(ed<op)ed+=n;
if(x<=op)x+=n;
return x<ed?(x-)%n+:(ed-)%n+;
}
void print(int x)
{
if(x<)printf("%d\n",x);
else printf("+%d\n",x);
}
void rua(int k,int cur)
{
if(k==m)return;
int i=cur?cur:s,cnt=,P=di[cur][nxt[cur]];
if(a[i]==k+)print(),vis[i]=;
while(i!=l[cur][nxt[cur]])
{
i+=P,i=(i+n-)%n+,cnt++;
if(a[i]==k+ && !vis[i])
print(cnt*P),cnt=,vis[i]=;
}
P*=-;
while(i!=nxt[cur])
{
i+=P,i=(i+n-)%n+,cnt++;
if(a[i]==k+ && !vis[i])
print(cnt*P),cnt=;
}
rua(k+,i);
}
int main()
{
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),p[i]=a[i];
sort(p+,p+n+);
m=unique(p+,p+n+)-p-;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(a[i]==p[j])
{
d[j].push_back(i);
a[i]=j;break;
}
d[].push_back(s);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dis[i][j]=(j+n-i)%n;
for(int i=;i<m;i++)
{
int sz=d[i+].size();
for(auto j:d[i])
for(int k=;k<sz;k++)
{
int to=d[i+][k];
int last=check1(j,to,d[i+][(k+sz-)%sz]);
g[j][to]=dis[j][last]+dis[to][last],l[j][to]=last,di[j][to]=;
last=check2(to,j,d[i+][(k+)%sz]);
if(g[j][to]>dis[last][j]+dis[last][to])
g[j][to]=dis[last][j]+dis[last][to],l[j][to]=last,di[j][to]=-;
if(j==to)
g[j][to]=*min(dis[j][d[i+][(k+sz-)%sz]],dis[d[i+][(k+)%sz]][j]),
g[j][to]=min(g[j][to],n);
if(i==)g[][to]=g[j][to],l[][to]=l[j][to],di[][to]=di[j][to];
}
}
d[].pop_back();
d[].push_back();
for(auto i:d[m])f[i]=;
for(int i=m-;i>=;i--)
for(auto j:d[i])
for(auto k:d[i+])
if(f[j]>f[k]+g[j][k])
f[j]=f[k]+g[j][k],nxt[j]=k;
printf("%d\n",f[]);
rua(,);
}