首页 > 代码库 > 2014 ACM/ICPC Asia Regional Xi'an Online
2014 ACM/ICPC Asia Regional Xi'an Online
A Post Robot
。。。嗯，比赛时手拍了一个自动机，注意是手拍。。= =
1 /* 2 ID:esxgx1 3 LANG:C++ 4 PROG:A 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm>10 using namespace std;11 12 char str[10007];13 14 int main(void)15 {16 #ifndef ONLINE_JUDGE17 freopen("in.txt", "r", stdin);18 #endif19 while(gets(str) != NULL) {20 int dd = 0;21 for(int i = 0; str[i]; ++i) {22 _failed:23 //printf("%c %d\n", str[i], dd);24 if (dd == 0) {25 if (str[i] == ‘A‘) dd = 1;26 else if (str[i] == ‘i‘) dd = 5;27 else if (str[i] == ‘S‘) dd = 11;28 }29 else if (dd == 1) {30 if (str[i] == ‘p‘) dd = 2;31 else {dd = 0; goto _failed;}32 }33 else if (dd == 2) {34 if (str[i] == ‘p‘) dd = 3;35 else {dd = 0; goto _failed;}36 }37 else if (dd == 3) {38 if (str[i] == ‘l‘) dd = 4;39 else {dd = 0; goto _failed;}40 }41 else if (dd == 4) {42 dd = 0;43 if (str[i] == ‘e‘) printf("MAI MAI MAI!\n");44 else {dd = 0; goto _failed;}45 }46 else if (dd == 5) {47 if (str[i] == ‘P‘) dd = 6;48 else {dd = 0; goto _failed;}49 }50 else if (dd == 6) {51 if (str[i] == ‘h‘) dd = 7;52 else if (str[i] == ‘a‘) dd = 10;53 else if (str[i] == ‘o‘) dd = 10;54 else {dd = 0; goto _failed;}55 }56 else if (dd == 7) {57 if (str[i] == ‘o‘) dd = 8;58 else {dd = 0; goto _failed;}59 }60 else if (dd == 8) {61 if (str[i] == ‘n‘) dd = 9;62 else {dd = 0; goto _failed;}63 }64 else if (dd == 9) {65 dd = 0;66 if (str[i] == ‘e‘) printf("MAI MAI MAI!\n");67 else {dd = 0; goto _failed;}68 }69 else if (dd == 10) {70 dd = 0;71 if (str[i] == ‘d‘) printf("MAI MAI MAI!\n");72 else {dd = 0; goto _failed;}73 }else if (dd == 11) {74 if (str[i] == ‘o‘) dd = 12;75 else {dd = 0; goto _failed;}76 } else if (dd == 12) {77 if (str[i] == ‘n‘) dd = 13;78 else {dd = 0; goto _failed;}79 } else if (dd == 13) {80 dd = 0;81 if (str[i] == ‘y‘) printf("SONY DAFA IS GOOD!\n");82 else {dd = 0; goto _failed;}83 }84 }85 }86 return 0;87 }
C Paint Pearls
状态方程好想，但预处理真的不是很容易。简单来说预处理用到了一个单调性，即颜色不同的越多越要往回看。
具体分析干脆引用某大神的：
状态转移方程很好想，dp[i] = min(dp[j]+o[j~i]^2,dp[i]) ,o[j~i]表示从j到i颜色的种数。
普通的O（n*n）是会超时的，可以想到o[]最大为sqrt(n),问题是怎么快速找到从i开始往前2种颜色、三种、四种。。。o[]种的位置。
离散化之后，可以边走边记录某个数最后一个出现的位置，初始为-1，而所要求的位置就等于
if(last[a[i]]==-1) 该数没有出现过，num[i][1] = i,num[i][j+1] = num[i-1][j];
else last[a[i]]之前 num[i][1] = i,num[i][j+1] = num[i-1][j],之后num[i][j]= num[i-1][j];
当然赛时我这个渣渣是肯定写不出来的，后来看了这个分析写了一份代码，个人感觉按这个思路真的不是很好写（也许应该看看thu的那份）：
/*ID:esxgx1LANG:C++PROG:xian_C*/#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define NN 500007int coloridx[NN], color[NN], ncolors;int cpre[NN]; // 某个颜色上一次出现的位置int clbck[NN]; // n颜色回溯int _dp[NN+1], *dp = &_dp[1];int main(void){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int N; while(scanf("%d", &N) > 0) { for(int i=0; i<N; ++i) { scanf("%d", &color[i]); coloridx[i] = color[i]; } // 颜色离散化 sort(color, color + N); ncolors = unique(color, color + N) - color; for(int i=0; i<N; ++i) coloridx[i] = lower_bound(color, color + ncolors, coloridx[i]) - color; memset(clbck, -1, sizeof(clbck)); memset(cpre, -1, sizeof(cpre)); clbck[1] = cpre[coloridx[0]] = 0; dp[0] = 1; for(int i=1; i<N; ++i) { dp[i] = 0x3f3f3f3f; if (cpre[coloridx[i]] != i-1) { if (cpre[coloridx[i]] < 0) { // 颜色没出现过 for(int j = sqrt(N); j>0; --j) clbck[j+1] = clbck[j]; } else { int j = sqrt(N) + 1; for(; j > 0 && (clbck[j] < 0 || clbck[j] <= cpre[coloridx[i]]); --j); for(--j; j > 0 && clbck[j] > cpre[coloridx[i]]; --j) clbck[j+1] = clbck[j]; } clbck[1] = i; } for(int j = 1; clbck[j] >= 0; ++j) { dp[i] = min(dp[i], dp[clbck[j]-1] + j*j); //printf("(%d) j=%d %d [pre%d]\n", i+1, j, clbck[j]+1, cpre[coloridx[i]] + 1); } //printf("%d %d\n", i, dp[i]); cpre[coloridx[i]] = i; } printf("%d\n", dp[N-1]); } return 0;}
E Game
真的很凑巧，这题是我们的省赛原题，然后又yy了一份代码。。
#include <cstdio>using namespace std; int N; int main(){ while(scanf("%d", &N) > 0) { int i, j; j = 0; for(i=0; i<N; ++i) { int k; scanf("%d", &k); j ^= k; } printf(j? "Win\n" : "Lose\n"); } return 0;}
H Number Sequence
#include<cstdio>#include<cstring>using namespace std;int n;long long ans[100007];int a[100007];int main(){ int i; long long x,sum; while (scanf("%d",&n) > 0) { for(int i=0; i<=n; ++i) scanf("%d", &a[i]); x = 1; while (x<=n) x <<= 1; x--; memset(ans,-1,sizeof(ans)); for (i=n; i>=0; --i) { if (ans[i]!=-1) continue; while ((x^i)>n || ans[x^i]!=-1) x>>=1; ans[x^i]=i,ans[i]=x^i; } sum=0; for (i=0; i<=n; ++i) sum+=i^ans[i]; printf("%I64d\n",sum); for (i=0;i<=n;i++) { if (i) putchar(‘ ‘); printf("%I64d",ans[a[i]]); } putchar(‘\n‘); } return 0;}
I 233 Matrix
快速幂，神队友脑洞大开yy了这个矩阵，然后就没有然后了。。
1 /* 2 ID:esxgx1 3 LANG:C++ 4 PROG:I 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm>10 using namespace std;11 12 13 #define MM 1714 15 struct matrix {16 long long m[MM][MM];17 };18 19 #define MOD 1000000720 21 int Nn;22 23 struct matrix m_mult(const struct matrix &a, const struct matrix &b)24 {25 struct matrix r;26 for(int i=0; i<Nn; ++i) {27 for(int j=0; j<Nn; ++j) {28 r.m[i][j] = 0;29 for(int k = 0; k < Nn; ++k) {30 r.m[i][j] += a.m[i][k] * b.m[k][j];31 r.m[i][j] %= MOD;32 }33 }34 }35 return r;36 }37 38 struct matrix m_pow(struct matrix a, int n)39 {40 struct matrix p;41 memset(&p, 0, sizeof(p));42 for(int i=0; i<Nn; ++i)43 p.m[i][i] = 1;44 while(n) {45 if (n & 1) p = m_mult(p, a);46 a = m_mult(a, a);47 n >>= 1;48 }49 return p;50 }51 52 int main(void)53 {54 #ifndef ONLINE_JUDGE55 freopen("in.txt", "r", stdin);56 #endif57 58 int N, M;59 while(scanf("%d%d", &N, &M) > 0) {60 ++N;61 matrix p;62 memset(&p, 0, sizeof(p));63 for(int i=0; i < N; ++i) {64 p.m[i][0] = 10;65 for(int j=1; j<=i; ++j)66 p.m[i][j] = 1;67 p.m[i][N] = 1;68 }69 p.m[N][N] = 1, Nn = N+1;70 p = m_pow(p, M);71 72 matrix q;73 memset(&q, 0, sizeof(q));74 q.m[0][0] = 23, q.m[N][0] = 3;75 for(int i=1; i<N; ++i)76 scanf("%I64d", &q.m[i][0]);77 p = m_mult(p, q);78 //p = q;79 printf("%d\n", p.m[N-1][0]);80 }81 return 0;82 }
2014 ACM/ICPC Asia Regional Xi'an Online
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。