WC 2010シーケンサ
12868 ワード
データの特徴
1.小さいデータ√
2.ランダム√3.ランダム√4.チェーン√5.tarjan √ 6.菊花図√7.菊花図√8.満二叉木√9.満二叉木√10.完全二叉木√
ひとつひとつ言う
1.手で遊べばいい
2.検索手動反復の深さ
4.データはチェーンです.暴力がバブルを起こす
5.データは完全図で、tarjanは連通成分を強く走って、各成分は単独でやります
tarjan
答え
8.初めて見ると規則がないので,問題の中でまた採点基準を君にあげた.
完璧ではないアルゴリズムになると思います
明らかにデータは木です
まずbfsを書いて深さを見て
1.小さいデータ√
2.ランダム√3.ランダム√4.チェーン√5.tarjan √ 6.菊花図√7.菊花図√8.満二叉木√9.満二叉木√10.完全二叉木√
ひとつひとつ言う
1.手で遊べばいい
2.検索手動反復の深さ
//Copyright(c)2016 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int n,m;
int a[10001];
int move[100][100];
int t[100];
int pos[100];
int p[100];
void ch2(int i){
int tmp=pos[move[i][1]];
for(int j=1;j<t[i];j++){
pos[move[i][j]]=pos[move[i][j+1]];
}
pos[move[i][t[i]]]=tmp;
for(int j=1;j<=n;j++){
p[pos[j]]=j;
}
}
void ch1(int i){
int tmp=pos[move[i][t[i]]];
for(int j=t[i];j>1;j--){
pos[move[i][j]]=pos[move[i][j-1]];
}
pos[move[i][1]]=tmp;
for(int j=1;j<=n;j++){
p[pos[j]]=j;
}
}
bool flag=false;
void dfs(int step){
if(step>4)return;
for(int i=1;i<=n;i++){
if(pos[i]!=i)goto end;
}
flag=true;return;
end:;
for(int i=1;i<=m;i++){
ch1(i);
dfs(step+1);
if(flag){
printf("%d
",i);
return;
}
ch2(i);
}
}
int main(){
freopen("sort2.in","r",stdin);
freopen("sort2.tt","w",stdout);
splay(n);splay(m);
for(int i=1;i<=n;i++){
splay(a[i]);
pos[a[i]]=i;p[i]=a[i];
}
for(int i=1;i<=m;i++){
splay(t[i]);
for(int j=1;j<=t[i];j++){
splay(move[i][j]);
}
}
dfs(0);
for(int i=1;i<=n;i++){
fprintf(stderr,"%d ",p[i]);
}
ch1(7);
fprintf(stderr,"
");
for(int i=1;i<=n;i++){
fprintf(stderr,"%d ",p[i]);
}
ch2(7);
fprintf(stderr,"
");
for(int i=1;i<=n;i++){
fprintf(stderr,"%d ",p[i]);
}
fprintf(stderr,"
");
}4.データはチェーンです.暴力がバブルを起こす
//Copyright(c)2016 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int n,m;
int a[10001];
int pos[1001];
int move[1001];
int ans[1000001],t;
int main(){
freopen("sort4.in","r",stdin);
freopen("sort4.out","w",stdout);
splay(n);splay(m);
for(int i=1;i<=n;i++){
splay(a[i]);pos[a[i]]=i;
}
for(int i=1;i<=m;i++){
int x,y;splay(x),splay(x),splay(y);
move[x]=i;
}
for(int i=1;i<=n;i++){
for(int j=a[i]-1;j>=i;j--){
ans[++t]=move[j];
swap(pos[j],pos[j+1]);
a[pos[j]]=j,a[pos[j+1]]=j+1;
}
}
printf("%d
",t);
for(int i=1;i<=t;i++){
printf("%d
",ans[i]);
}
for(int i=1;i<=n;i++){
fprintf(stderr,"%d ",a[i]);
}
}5.データは完全図で、tarjanは連通成分を強く走って、各成分は単独でやります
tarjan
//Copyright (c)2015 Liu chenrui
//This sourcecode is licensed under Dev c++ 5.4.0
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#define inf 1000000000 //inf + inf < maxlongint
using namespace std;
int getint()
{
int _b=0;char _c;
for (_c=getchar();_c<'0'||_c>'9';_c=getchar());
for (;_c>='0'&&_c<='9';_c=getchar())
{_b*=10;
_b+=_c-'0';
}
return _b;
}
int low[1010],dfn[1010];
int n,m;
int tim=0;
int first[1010];
int sta[1010],tin=0;
int x,y,size;
int insta[1010];
struct yyy{int next,to,from;}bian[2010];
int ans=0;
void inser(int x,int y)
{
size++;
bian[size].next=first[x];
bian[size].to=y;
bian[size].from=x;
first[x]=size;
}
void tarjan(int p)
{
dfn[p]=low[p]=++tim;
sta[++tin]=p;
insta[p]=tin;
int u=first[p];
int o=0;
while(u!=0)
{
int p1=bian[u].to;
if(dfn[p1]==0)
{
tarjan(p1);
low[p]=min(low[p1],low[p]);
}
else
{
if(insta[p1]!=0)
{
low[p]=min(low[p],dfn[p1]);
}
}
u=bian[u].next;
}
if(low[p]==dfn[p])
{
//ans++;
int c;
c=insta[p];
if(c!=0)
{
printf(" %d :",ans+1);
for(int j=c;j<=tin;j++)
printf("%d ",sta[j]),insta[sta[j]]=0,sta[j]=0;
printf("
");
tin=c-1;
ans++;
}
}
}
int main()
{
freopen("sort5.in","r",stdin);
freopen("sort5.out","w",stdout);
m=getint();n=getint();
n=500,m=500;
for(int i=1;i<=n;i++)
{
x=getint();
inser(i,x);
}
for(int i=1;i<=m;i++)
{
if(dfn[i]==0)tarjan(i);
}
cout<<ans<<endl;
return 0;
}答え
//Copyright(c)2016 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
inline void splay(int &v){
v=0;char c=0;int p=1;
while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
v*=p;
}
int n,m;
int a[10001];
int x[200000];
int y[200000];
int to[505][505];
int main(){
freopen("sort5.in","r",stdin);
freopen("sort5.out","w",stdout);
splay(n);splay(m);
for(int i=1;i<=n;i++){
splay(a[i]);
if(a[i]==i){
fprintf(stderr,"%d
",a[i]);
}
}
for(int i=1;i<=m;i++){
int x,y;splay(x),splay(x),splay(y);
to[x][y]=to[y][x]=i;
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
if(!to[i][j]){
fprintf(stderr,"%d %d
",i,j);
}
}
}*/
freopen("sort5.tt","r",stdin);
printf("490
");
for(int i=1;i<=10;i++){
int t=0;
while(1){
splay(a[++t]);
if(a[t]==1000)break;
}
t--;
for(int i=1;i<=t-1;i++){
printf("%d
",to[a[i]][a[i+1]]);
}
}
}8.初めて見ると規則がないので,問題の中でまた採点基準を君にあげた.
完璧ではないアルゴリズムになると思います
明らかにデータは木です
まずbfsを書いて深さを見て
<pre name="code" class="cpp">
//Copyright(c)2016 liuchenrui
#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
inline void splay(int &v){
<span style="white-space:pre"> </span>v=0;char c=0;int p=1;
<span style="white-space:pre"> </span>while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
<span style="white-space:pre"> </span>while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
<span style="white-space:pre"> </span>v*=p;
}
struct Edge{
<span style="white-space:pre"> </span>int to,next;
}edge[80010];
int size,first[40010];
int a[40010],b[40010];
void addedge(int x,int y){
<span style="white-space:pre"> </span>//fprintf(stderr,"%d %d %d %d
",x,y,a[x],a[y]);
<span style="white-space:pre"> </span>size++;
<span style="white-space:pre"> </span>edge[size].to=y;
<span style="white-space:pre"> </span>edge[size].next=first[x];
<span style="white-space:pre"> </span>first[x]=size;
}
int dl[40010];
bool vis[40010];
int deep[40010];
void bfs(){
<span style="white-space:pre"> </span>int head=0,tail=1;
<span style="white-space:pre"> </span>dl[1]=1;deep[1]=1;vis[1]=true;
<span style="white-space:pre"> </span>while(head!=tail){
<span style="white-space:pre"> </span>int v=dl[++head];
<span style="white-space:pre"> </span>for(int u=first[v];u;u=edge[u].next){
<span style="white-space:pre"> </span>if(!vis[edge[u].to]){
<span style="white-space:pre"> </span>vis[edge[u].to]^=1;
<span style="white-space:pre"> </span>dl[++tail]=edge[u].to;
<span style="white-space:pre"> </span>deep[edge[u].to]=deep[v]+1;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
}
int main(){
<span style="white-space:pre"> </span>freopen("sort10.in","r",stdin);
<span style="white-space:pre"> </span>freopen("test.out","w",stdout);
<span style="white-space:pre"> </span>int n,m;splay(n);splay(m);
<span style="white-space:pre"> </span>for(int i=1;i<=n;i++){
<span style="white-space:pre"> </span>splay(b[i]);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>for(int i=1;i<=n;i++){
<span style="white-space:pre"> </span>a[b[i]]=i;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>for(int i=1;i<=m;i++){
<span style="white-space:pre"> </span>int x,y;splay(x),splay(x),splay(y);
<span style="white-space:pre"> </span>addedge(x,y);addedge(y,x);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>bfs();
<span style="white-space:pre"> </span>for(int i=1;i<=n;i++){
<span style="white-space:pre"> </span>printf("%d ",dl[i]);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>printf("
");
<span style="white-space:pre"> </span>for(int i=1;i<=n;i++){
<span style="white-space:pre"> </span>printf("%d ",deep[i]);
<span style="white-space:pre"> </span>}
}
发现深度是1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6猜想是满二叉树
跑了一下发现的确是
那么就每次选一个当前最深的点把他移到合适的位置就好了
//Copyright(c)2016 liuchenrui #include<cstdio> #include<ctime> #include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; inline void splay(int &v){ v=0;char c=0;int p=1; while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();} while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();} v*=p; } int a[40010],b[40010]; int val[40010]; bool mark[40010]; int move[40010]; vector <int> ans; int n,m; void calc(int now){ int t; for(int i=1;i<=n;i++){ if(a[i]==now){ t=i;break; } } if(t==now)return; int l=t,r=now; memset(mark,0,sizeof mark); if(val[l]<val[r])swap(l,r); //cerr<<l<<" "<<r<<endl;exit(0); while(val[l]!=val[r]){ mark[l]=1; l>>=1; } while(l!=r){ mark[l]=1;mark[r]=1; l>>=1;r>>=1; } mark[l]=1; while(t!=now){ int nxt;mark[t]=0; if(mark[t>>1])nxt=(t>>1); if(mark[t<<1])nxt=(t<<1); if(mark[t<<1|1])nxt=(t<<1|1); if(nxt>t)ans.push_back(nxt); else ans.push_back(t); swap(a[t],a[nxt]);t=nxt; } } int main(){ freopen("sort8.in","r",stdin); freopen("test.out","w",stdout); for(int i=1;i<=40000;i++){ val[i]=(val[i>>1])+1; } splay(n);splay(m); for(int i=1;i<=n;i++){ splay(b[i]); } for(int i=1;i<=n;i++){ a[b[i]]=i; } for(int i=1;i<=m;i++){ int x,y;splay(x);splay(x);splay(y); move[x]=i; } for(int i=n;i>=1;i--){ calc(i); } printf("%d
",ans.size()); for(int i=0;i<ans.size();i++){ printf("%d
",move[ans[i]],ans[i]); } }
9,10は上のものと同じです
大小は20余りのプログラムを書いて、、答えはやはり各種の私達です
初めてAが答えを落とした.題名を書いて記念にする