摘要
本文主要给出了2018 ACM-ICPC Asia Beijing Regional Contest的部分题解，意即熟悉区域赛题型，保持比赛感觉。
Jin Yong’s Wukong Ranking List
题意
输入关系组数n和n组关系，每组关系是s1 > s2，问第一出现矛盾的组，或者没有矛盾就输出0.
解题思路
第一感觉是拓扑排序，未完，又写了一个深搜的传递闭包，1 A，和2018年河南省赛的题很像。
代码
#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <iostream>
using namespace std; const int maxn = ; int e[maxn][maxn];
int n, r;
bool f;
map<string, int> mp; void F(int a, int u) {
//printf("%d %d\n", a, u);
if(e[u][a]) {
f = ;
return;
}
e[a][u] = ;
for(int i = ; i < r; i++) {
if(e[u][i]) {
F(a, i);
if(f)
return;
}
}
} int main()
{
char s1[maxn], s2[maxn];
string s3, s4, s5, s6;
while(scanf("%d", &n) != EOF) {
mp.clear();
memset(e, , sizeof(e));
r = ;
f = ; for(int i = ; i < n; i++) {
scanf("%s%s", s1, s2);
s3 = s1;
if(mp.find(s3) == mp.end()) {
mp[s3] = r++;
}
s4 = s2;
if(mp.find(s4) == mp.end()) {
mp[s4] = r++;
}
if(f == ) {
F(mp[s3], mp[s4]);
if(f == ) {
s5 = s3;
s6 = s4;
}
}
}
if(f)
cout<<s5<<" "<<s6<<endl;
else
printf("0\n");
}
return ;
}
题意
输出第k个回文数
解题思路
因为k的位数最长是1e5，所以试图根据给出的k找到结果，打表找出两者之间的规律。
首先长度为1时，减1输出；
然后s[0] == '1' && s[1] == '0'时，用9替换这两位，找规律回文输出；（注意特判一下10的情况）
再然后s[0] == '1' && s[1] == 'x'时（其中x是1到9任意一个数字），去掉s[0]，找规律回文输出；
最后将s[0] - 1，找规律回文输出。
代码
#include <cstdio>
#include <cstring> const int maxn = 1e5 + ;
char s[maxn]; int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", &s);
int l = strlen(s);
if(l == )
printf("%d\n", s[] - '' - );
else if(s[] == '' && s[] == '') {
putchar('');
if(l > ) {
for(int i = ; i < l; i++) {
printf("%c", s[i]);
}
for(int i = l - ; i >= ; i--) {
printf("%c", s[i]);
}
putchar('');
}
puts("");
}
else if(s[] == '') {
for(int i = ; i < l; i++) {
printf("%c", s[i]);
}
for(int i = l - ; i >= ; i--) {
printf("%c", s[i]);
}
puts("");
} else {
putchar((s[] - '' - ) + '');
for(int i = ; i < l; i++) {
printf("%c", s[i]);
}
for(int i = l - ; i >= ; i--) {
printf("%c", s[i]);
}
putchar((s[] - '' - ) + '');
puts("");
}
}
return ;
}
题意
给出从0上到200的方案数n，求搭建哪几条通道能够使得方案数恰好为n
解题思路
由于多种方案输出任意一种均可，所以我们采用先使用传送门，然后用后面的台阶凑方案数的方法，每次找到小于等于n离最近的斐波那契数F[x]，然后连接1到(200 - x)，然后跳过2，如果还需凑数，再找到小于等于离n - F[x]最近的斐波那契数F[y]，然后3连接到(200 - y)，直到凑够为止，最后添加一条下一个台阶自闭的通道即可。
代码
#include <cstdio>
#include <vector>
using namespace std; typedef long long ll;
typedef pair<ll, ll> pir; ll f[]; ll id(ll x) {
for(int i = ; i < ; i++) {
if(x < f[i]) {
return i - ;
}
}
} int main()
{
f[] = ;
f[] = ;
for(int i = ; i < ; i++) {
f[i] = f[i - ] + f[i - ];
} ll n;
vector<pir> v;
while(scanf("%lld", &n) != EOF) {
if( == n) {
printf("2\n1 1\n2 2\n");
continue;
}
v.clear();
ll i;
for(i = ; ; i += ) {
int x = id(n);
v.push_back(pir(i, - x));
n -= f[x];
if( == n)
break;
}
v.push_back(pir(i + , i + )); printf("%d\n", v.size());
for(i = ; i < v.size(); i++) {
printf("%lld %lld\n", v[i].first, v[i].second);
}
}
return ;
}
题意
输入一些含有空格，数字和小写字母的字符，计算并输出有哪些actual数
解题思路
细节题，先整合成一行字符处理，具体就是前一行末尾是数字并且后一行开头是数字就直接连接，否则加一个空格分开。然后记录每个字母在哪一行上，便于最后输出。最后分隔判断处理。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN=;
int num[MAXN];
vector<ll> ans;
int pos[MAXN];
string str; pair<ll,int> check(int l,int r){ for(int i=l;i<=r;i++){
if(str[i]>='a'&&str[i]<='z')
return {-,};
} ll cur=;
if(str[l]==''&&l==r){
return {,pos[l]};
}
else{
if(str[l]==''&&l!=r)
return {-,};
} for(int i=l;i<=r;i++){
cur=cur*10ll+ll(str[i]-'');
}
return {cur,pos[l]};
} int main(){ char c;
int line=;
int len=;
char last=; while(~scanf("%c",&c)){
if(c=='\n')
{
if(last>='a'&&last<='z'){
str.push_back(' ');
pos[len++]=line;
}
line++;
}
else{ if(last=='\n'&&c>='a'&&c<='z'){
str.push_back(' ');
pos[len++]=line;
} str.push_back(c);
pos[len++]=line;
}
last=c;
}
str.push_back(' ');
pos[len++]=line; int l=-,r=-;
for(int i=;i<len;i++){
if((str[i]>='a'&&str[i]<='z')||(str[i]>=''&&str[i]<='')){
if(l==-){
l=i;
}
}
else{
if(l!=-){
r=i-;
pair<ll,int> t=check(l,r);
if(t.first!=-){
num[t.second]++;
ans.push_back(t.first);
}
l=-,r=-;
}
}
} for(int i=;i<ans.size();i++){
if(ans.size()-==i)
cout<<ans[i]<<endl;
else
cout<<ans[i]<<" ";
} for(int i=;i<=line;i++)
cout<<num[i]<<endl; return ;
}