codeforces 125 A-E 補題

A?Measuring Lengths in Baden

進制轉換 水題

#include<bits/stdc++.h>
using namespace std;int main()
{int n;scanf("%d",&n);int a=n/36;n-=a*36;int b=(n)/3;if((n%3)>=2)b++;while(b>=12)b-=12,a+=1;printf("%d %d\n",a,b);return 0;
}

B?Simple XML

用棧實現的括號匹配相信大家都會?

當然所有棧都可以用更直接粗暴的方法實現。

#include <iostream>using namespace std;int main()
{string s; int x=0,y=0;cin >> s;for(int i=0; s[i]; i++)if(s[i]=='>'){if(s[i-2]=='/')y-=2;for(int i=0; i<y; i++)cout<<" ";for(int j=x; j<=i; j++)cout<<s[j]; cout<<endl;if(s[i-2]!='/')y+=2;x=i+1;}
}

C?Hobbits' Party

很簡單的貪心構造

#include<bits/stdc++.h>
using namespace std;const int N=500;
vector<int> gues[N];
int main()
{gues[1].resize(2);gues[2].resize(2);gues[3].resize(2);gues[1][0]=1;gues[1][1]=2;gues[2][0]=1;gues[2][1]=3;gues[3][0]=2;gues[3][1]=3;int k;scanf("%d",&k);k-=3;int t=3;int i;for( i=4;;i++){if((i-1)>k)break;for(int j=1;j<=i-1;j++){gues[j].push_back((t+j));gues[i].push_back((t+j));}t+=(i-1);k-=(i-1);}printf("%d\n",i-1);for(int j=1;j<i;j++){for(int k=0;k<gues[j].size();k++)printf("%d ",gues[j][k]);printf("\n");}return 0;
}

　　

D?Two progressions

給定一個序列 試問能否將它拆分成兩個等差數列 滿足元素之間的相對位置不改變

暴力分配每個元素屬于第一個還是第二個序列即可

剪枝：每個元素對于每個公差的序列只用搜索一次（證明方法自己思考）

#include<cstdio>
#include<set>
using namespace std;int n, al, bl, ff, i; 
int s[30000], a[30000], b[30000];
set<int> visa[30000], visb[30000];void dfs(){if(al == n) return;if(al + bl == n) {ff = 1; return;}if(al < 2 || s[al+bl]-a[al-1] == a[al-1]-a[al-2] && (visb[al+bl].find(a[al-1]-a[al-2])==visb[al+bl].end())){a[al] = s[al+bl];if(al>1) visa[al+bl].insert(a[al]-a[al-1]);al++;dfs();if(ff) return;al--;}if(bl < 2 || s[al+bl]-b[bl-1] == b[bl-1]-b[bl-2] && (visa[al+bl].find(b[bl-1]-b[bl-2])==visa[al+bl].end())){b[bl] = s[al+bl];if(bl>1) visb[al+bl].insert(b[bl]-b[bl-1]);bl++;dfs();if(ff) return;bl--;}
}int main(){scanf("%d", &n);for(i = 0; i < n; i++)scanf("%d", &s[i]);ff = al = bl = 0;dfs();if(ff){for(i = 0; i < al; i++)printf("%d ", a[i]);printf("\n");for(i = 0; i < bl; i++)printf("%d ", b[i]);printf("\n");}elseprintf("No solution\n");return 0;
}

　　

E?MST Company

傳送門