2012 ACM HCPC spring 今天顺利落幕了，除了有两个题题目描述有些问题之外，其他的貌似还不错！
现在我为了无耻地吸引广大不明真相的群众前来围观，故抢先发出一篇山寨版解题报告。事先声明此报告与HIT ACM Group官方无任何关系，里面所有的文字叙述均为本人道听途说妄加揣测的结果，里面所有的代码均为本人利用职务之便窃取广大验题群众的劳动果实而获得！
下面是每个题的简单报告和代码
作者：luyi0619，不知道怎么做，xiaodai神牛在验题后传说用了一种OI通用的方法被卡了时间，于是lu大神执意要放在第一题的位置卡wwqqss神牛，结果被16min就秒了，情何以堪。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
/*This Code is Submitted by luyi0619 for Problem 4000276 at 2012-05-19 12:29:49*/ #include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int N = 100010; struct Node { long long x,y; long long ansx; long long ansy; } node[N]; bool cmpx(Node a,Node b) { return a.x < b.x; } bool cmpy(Node a,Node b) { return a.y < b.y; } int main() { //ios::sync_with_stdio(false); int n , t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i = 0 ; i < n ; i ++) { int u , v; scanf("%d %d",&u,&v); node[i].x = (u + v); node[i].y = (u - v); node[i].ansx = 0; node[i].ansy = 0; } sort(node,node + n,cmpx); for(int i = 1 ; i < n ; i ++) { node[0].ansx += node[i].x - node[0].x; } for(int i = 1 ; i < n ; i ++) { node[i].ansx += node[i-1].ansx - (node[i].x-node[i-1].x) * (n - i) + (node[i].x-node[i-1].x) * i; } sort(node,node + n,cmpy); for(int i = 1 ; i < n ; i ++) { node[0].ansy += node[i].y - node[0].y; } for(int i = 1 ; i < n ; i ++) { node[i].ansy += node[i-1].ansy - (node[i].y-node[i-1].y) * (n - i) + (node[i].y-node[i-1].y) * i; } int k = 0; for(int i = 1 ; i < n ; i ++) { if(node[i].ansx + node[i].ansy < node[k].ansx + node[k].ansy) { k = i; } } printf("%lld\n",(node[k].ansx + node[k].ansy) / 2 ); } return 0; } |
B-Set S
作者：NightBalance，简单题，可以直接用优先队列每次取S中的数然后求2x+1和3x＋1放回优先队列即可，更好的方法是设两个游标纪录S中由小到大的数是否已经被*2/*3，可以O(n)得出结果。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include
#include
using namespace std;
unsigned int a[1000000];
int n;
void Init()
{
int i,j,k,t1,t2;
a[j=i=0]=1;
for(k=1;k<1000000;k++)
<!--1000000--> {
t1=2*a[i]+1;
t2=3*a[j]+1;
if(t1==t2)
{
a[k]=t1;
i++;j++;
continue;
}
a[k]=min(t1,t2);
if(a[k]==t1)
i++;
else
j++;
}
}
int main()
{
Init();
while(cin>>n)
cout< return 0;
} |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/*This Code is Submitted by icek for Problem 4000265 at 2012-05-16 21:51:00*/
#include
#include
#include
#include
#include
#include
<map> #include </map> <map> using namespace std;</map>
const int N = 1112;
priority_queue, greater> q;
long long ans[1000005];
int main()
{
q.push(4);
q.push(3);
int cnt = 2;
ans[1] = 1;
while ( cnt <= 1000001)
{
while (q.top() == ans[cnt - 1])
{
q.pop();
}
long long t = q.top();
//printf("%lld\n", t);
ans[cnt++] = t;
q.pop();
q.push(t * 2 + 1);
q.push(t * 3 + 1);
}
int n;
while ( scanf("%d", &n ) == 1 )
{
printf("%lld\n", ans[n]);
}
return 0;
} |
作者：NightBalance,简单DP，纪录2维状态，每次从两头转移。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
/*This Code is Submitted by lancelot for Problem 4000266 at 2012-05-15 19:56:55*/ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define MOD 1234567891 using namespace std; int num[2102]; int dp[1202][1002]; int n; int DP(int a,int b) { if(dp[a][b]) return dp[a][b]; if(a==b) { return dp[a][b]=num[a]*(n); } int d=n-b+a; int t=0; t=max(DP(a+1,b)+d*num[a],DP(a,b-1)+d*num[b]); return dp[a][b]=t; } int main() { while(scanf("%d",&n)==1&&n) { memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { scanf("%d",&num[i]); } printf("The Max Value Is %d.\n",DP(0,n-1)); } return 0; } |
作者：Yankaifyyy，图论，貌似解决一个有限制的最长路问题，可以用dijkstra解决。
PS.下面的代码与我无任何关系，只是我从后台随便找的，有什么问题直接去问rpk74m童鞋….
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
/*This Code is Submitted by rpk74m for Problem 4000269 at 2012-05-17 18:59:11*/ #include<cctype> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<iterator> #include<queue> #include<algorithm> #include<iostream> using namespace std; bool Rlx(double &w,double m){return m>w?(w=m,1):0;} struct Host{double w;string m;}N[500]; bool operator<(const Host &A,const Host &B){return B.m<A.m;} int BS(int n,Host &H){return isdigit(H.m[0])?lower_bound(2+N,n+N,H)-N:"localhost"==H.m;} struct Route{int y,z;double w;}; bool operator<(const Route &A,const Route &B){return A.w<B.w;} vector<int>G[500]; double DijH(int m){ double D[500][101]={}; Route R={1,m,N[1].w}; priority_queue<Route>Q; vector<int>::iterator p; for(D[1][m]=R.w,Q.push(R);!Q.empty()&&(R=Q.top()).y;) if(Q.pop(),D[R.y][R.z]==R.w&&R.z--) for(p=G[R.y].begin();G[R.y].end()!=p;++p) if(Rlx(D[*p][R.z],R.w*N[*p].w)) Q.push((Route){*p,R.z,D[*p][R.z]}); return Q.empty()?0:R.w; } int main(void) { bool F[500][500]; char z; int t,c=0,n,m,q,x,y; double s; Host H; for(cin>>t;t^c;printf(s?"%.f%%\n":"Oh no! Fyyy cannot login in his favourite mud world!\n",100*s)){ for(cin>>n>>q>>m,y=n;y--;N[y].w*=.01) cin>>N[y].m>>N[y].w>>z; if(sort(N,n+N),"localhost"!=N[1].m) swap(N[0],N[1]); for(memset(F,0,n*sizeof(F[0]));q--;) if(cin>>H.m,x=BS(n,H),cin>>H.m,!F[x][y=BS(n,H)]) F[x][y]=1,G[x].push_back(y); for(printf("Case #%i: ",++c),s=DijH(m);n--;G[n].clear()); } return 0; } |
作者：阿姨洗铁路，概率+DP，本来会卡掉状态压缩DP，后来好像感觉太残忍了，就放宽了数据让过了， 我知道的就这么多了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
/*This Code is Submitted by discover for Problem 4000272 at 2012-05-17 13:09:15*/ #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <algorithm> #include <ctime> #include <cmath> #include <vector> #include <map> #include <ctime> #include <stack> using namespace std; const int N = 209; int n; int ar[N]; char s[N][20]; double dp[23][2]; double p[N]; int bit(int x, int n) { return x >> n & 1; } void DP() { for (int i = 0; i < 20; ++i) { dp[i][0] = dp[i][1] = 0; if (bit(ar[0], i)) dp[i][1] = 1; else dp[i][0] = 1; // if (i < 3)cout << dp[i][1] << endl; double one, zero; int t; for (int j = 0; j < n; ++j) { one = dp[i][1]; zero = dp[i][0]; dp[i][1] = dp[i][0] = 0; t = bit(ar[j + 1], i); if (s[j][0] == '&') { dp[i][t & 1] += one * (1.0 - p[j]); dp[i][t & 0] += zero * (1.0 - p[j]); } else if (s[j][0] == '|') { dp[i][t | 1] += one * (1.0 - p[j]); dp[i][t | 0] += zero * (1.0 - p[j]); } else if (s[j][0] == '^') { dp[i][t ^ 1] += one * (1.0 - p[j]); dp[i][t ^ 0] += zero * (1.0 - p[j]); } dp[i][1] += one * p[j]; dp[i][0] += zero * p[j]; // if (i < 3) cout << dp[i][1] << " " << dp[i][0]<<endl; } //if (i < 3) cout << endl; } } int main() { //freopen("in", "r", stdin); int tcas = 0; while (cin >> n) { for (int i = 0; i <= n; ++i) { scanf("%d", ar + i); } for (int j = 0; j < n; ++j) scanf("%s", s[j]); for (int j = 0; j < n; ++j) { scanf("%lf", p + j); } DP(); double ans = 0; for (int i = 0; i < 20; ++i) { ans += dp[i][1]*(1 << i); // cout << dp[i][1] << endl; } printf("Case %d:\n%lf\n", ++tcas, ans); } } |
作者：xiaodai，几何，防住了wwqqss神牛的AK。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/*This Code is Submitted by wujianan2007 for Problem 4000271 at 2012-05-12 23:05:37*/ #include <cstdio> #include <cmath> #define MAXN 1005 const double PI = acos(-1.0); int n; double R; double x[MAXN], y[MAXN], r[MAXN]; inline double sqr(double x) { return x*x; } inline double dis(double x1, double y1, double x2, double y2) { return sqrt(sqr(x1 - x2) + sqr(y1 - y2)); } inline double area(double a, double b, double c, double d, double e, double f) { double u = dis(a, b, c, d); double v = dis(a, b, e, f); double w = dis(c, d, e, f); double p = (u + v + w) / 2; return sqrt(p * (p - u)*(p - v)*(p - w)); } int main() { while (scanf("%d %lf", &n, &R) == 2) { for (int i = 0; i < n; i++) scanf("%lf%lf%lf", &x[i], &y[i], &r[i]); x[n] = x[0]; y[n] = y[0]; double ans = 0, rem = 2 * PI; for (int i = 0; i < n; i++) { double alpha = 2 * asin(dis(x[i], y[i], x[i + 1], y[i + 1]) / (r[i]*2)); rem -= alpha; ans += alpha * sqr(r[i] + R) / 2 - sin(alpha) * sqr(r[i]) / 2; } ans += rem * sqr(R) / 2; for (int i = 1; i < n - 1; i++) ans += area(x[0], y[0], x[i], y[i], x[i + 1], y[i + 1]); printf("%.2lf\n", ans); } return 0; } |
作者：luyi0619，排序之后求最长公共子串，判一下重复的数就可以了。
PS.xiaodai童鞋似乎做麻烦了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
/*This Code is Submitted by xiaodai for Problem 4000273 at 2012-05-17 10:28:40*/ #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int maxn = 35; int f[maxn][maxn][maxn]; vector<int> s1,s2,q1,q2; int n1,n2; bool cmp(int a,int b) { return a>b; } int main() { int cas; cin >> cas; while (cas--) { s1.clear(); s2.clear(); q1.clear(); q2.clear(); cin >> n1 >> n2; for (int i=0;i<n1;i++) { int tmp; cin >> tmp; s1.push_back(tmp); } for (int i=0;i<n2;i++) { int tmp; cin >> tmp; s2.push_back(tmp); } sort(s1.begin(),s1.end()); sort(s2.begin(),s2.end()); q1.push_back(*s1.begin()); for (unsigned i=1;i!=s1.size();++i) { if (s1[i]!=*q1.rbegin()) { q1.push_back(s1[i]); } } q2.push_back(*s2.begin()); for (unsigned i=1;i!=s2.size();++i) { if (s2[i]!=*q2.rbegin()) { q2.push_back(s2[i]); } } sort(q1.begin(),q1.end(),cmp); sort(q2.begin(),q2.end(),cmp); memset(f,0x80,sizeof(f)); for (unsigned i=0;i<=q1.size();++i) for (unsigned j=0;j<=q2.size();++j) f[i][j][0] = 0; for (unsigned i=0;i!=q1.size();++i) for (unsigned j=0;j!=q2.size();++j) for (unsigned k=1;k<=min(i,j)+1;++k) { if (i==5 && j==6 && k==6) { int brk = 0; } f[i+1][j+1][k] = max(f[i][j+1][k],f[i+1][j][k]); if (q1[i]==q2[j]) { f[i+1][j+1][k] = max(f[i+1][j+1][k],f[i][j][k-1]+q1[i]); } } int ans = 0; int ansl = 0; for (unsigned i=min(q1.size(),q2.size());i>0;--i) { if (f[q1.size()][q2.size()][i]>=0) { ansl = i; ans = f[q1.size()][q2.size()][i]; break; } } if (ansl) { cout << ans << endl; } else cout << "NONE" << endl; } return 0; } |
H-BWT
作者：Canoe，本来是防AK的，但貌似和OI撞题了，所以就不幸被秒了(T_T)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
/*This Code is Submitted by luyi0619 for Problem 4000277 at 2012-05-18 20:25:26*/ #include <iostream> #include <cstdio> #include <vector> #include <string> #include <algorithm> using namespace std; const int N = 26; const int M = 1000010; int pre[M]; char buffer[M]; void buildkmp(const string& mch) { int i = 1 , j = -1; pre[0] = -1; while(i < mch.size()) { while( j>=0 && mch[j + 1] != mch[i] ) j = pre[j]; if(mch[j+1] == mch[i]) j++; pre[i] = j; i ++; } } bool kmp(const string& str,const string& mch) { int i = 0, j = -1; while(i < str.size()) { while( j>=0 && mch[j + 1] != str[i] ) j = pre[j]; if(mch[j+1] == str[i]) j ++; if(j == mch.size() - 1) { j = pre[j]; return true; } i++; } return false; } int main() { ios::sync_with_stdio(false); string bwt; while(scanf("%s",buffer) == 1) { bwt = buffer; vector<int> vf[N]; vector<int> vbwt[N]; vector<int> mbwt(bwt.size() , 0); string sorted = bwt; sort(sorted.begin(),sorted.end()); for(int i = 0 ;i < bwt.size() ; i ++) { if(bwt[i] != '$') { mbwt[ i ] = vbwt[ bwt[i] - 'a' ].size(); vbwt[ bwt[i] - 'a' ].push_back(i); } } for(int i = 0 ;i < sorted.size() ; i ++) { if(sorted[i] != '$') { vf[ sorted[i] - 'a' ].push_back(i); } } string T; char ch = bwt[0]; int od = 0; for(int i = 1 ;i < bwt.size() ; i ++) { T += ch; int lft = vf[ch - 'a'][od]; ch = bwt[lft]; od = mbwt[lft]; } reverse(T.begin(),T.end()); int q; //cin >> q; scanf("%d",&q); while(q--) { string test; //cin >> test; scanf("%s",buffer); test = buffer; buildkmp(test); if(kmp(T,test)) cout << "YES" << endl; else cout << "NO" << endl; } } return 0; } |
作者：yangjing，听他说模拟一下就可以了，貌似是比较水的题，不过过的人不多。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
/*This Code is Submitted by rpk74m for Problem 4000286 at 2012-05-19 12:33:01*/ #include<cstring> #include<algorithm> #include<iostream> using namespace std; int main(void) { long c,n,m,i,j,Q[101]; for(cin>>c;c--;cout<<Q[m]<<'\n') for(cin>>n>>m,memset(Q,0,sizeof(Q));n--;) for(i=0;m^i++;Q[i]=j+max(Q[i],Q[i-1])) cin>>j; return 0; } |
J-(A-B)%C
作者：yangjing，签到题，读入数据之后输出((a-b)%c+c)%c(c+a-b)%c即可。
作者：benny391，贪心，先把所有钱给BOSS，然后找尽量少的钱还给benny391,这个环节可以贪心先找100的，然后有两种选择是尽量找50的，或是留一张50不找，然后依次找20,10,5,1的钱就可以了，具体的证明过几天可以看官方的报告。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/*This Code is Submitted by benny391 for Problem 4000275 at 2012-05-19 08:11:31*/ #include <stdio.h> #include <algorithm> using namespace std; const int value[]={1,5,10,20,50,100}; const int maxint=0x7f000000; int a[6],b[6],c,n; int calc(int c) { int tot=0; for (int i=5;i>=0;i--) { if (i==4) continue; int tmp=min(b[i],c/value[i]); tot+=tmp; c-=tmp*value[i]; } if (c!=0) return maxint; return tot; } int main() { scanf("%d",&n); while (n--) { int c; scanf("%d",&c); for (int i=0;i<6;i++) scanf("%d",&a[i]),c-=a[i]*value[i]; for (int i=0;i<6;i++) scanf("%d",&b[i]),b[i]+=a[i]; c=abs(c); int tmp=c-min(b[5],c/100)*100; int k=min(b[4],tmp/50); int ans1=k+calc(c-k*50); int ans2=maxint; if (k>0) ans2=k-1+calc(c-(k-1)*50); int ans3=maxint; if (k<b[4] && c-(k+1)*50>=0) ans3=k+1+calc(c-(k+1)*50); printf("%d\n",min(min(ans1,ans2),ans3)); } } |
这里是最后的Rank
后记：
这次校赛历经了3周的筹备，中间夹杂了编译考试，吉林省赛，体系结构考试，大菠萝3上市等等事情，除去比赛中发现的两处题意描述不清，基本上还是获得了一个比较完满的结局。
比赛共收到备选题17题，取了其中4题为热身赛题，11题为正赛题。在验题过程中统计共有18名用户提交298次。在此向各位出题人和验题人表示由衷的感谢，没有你们付出的劳动，就没有校赛这套题目。
所有被选入正赛的题目的作者都可以获得50元/题的补助，请各位出题人及时联系我。
这里特别感谢NightBalance同学，他一个人就出了6个备选题，并且非常认真负责地修改题目以使其满足比赛要求，光是其中有一个题就前后给了我7次题面和数据。
还要感谢管理602机房的飞哥，他在比赛前用了整整两天加一个早上组织人将602机房布置整齐并配置好了所有的比赛环境，没有他就没有这次校赛干净整齐的比赛场地。
最后感谢所有HIT ACM Group的同学，大家都为准备这次校赛尽了自己的力量，出题，验题，海报，网络，气球，解答，每个环节都有大家的身影，ACM Group离不开你们每一个人！
－－－－－－－－－－－－－－我是开始扯淡的分界线－－－－－－－－－－－－－
做为现任ACM Group管理员（又名苦力员），我常常在想我为啥要来干这个吃力不讨好的工作。纠结了半天，原来是上学期退役之后觉得这个活应该挺好玩所以就接手了，之后就总是一种上了贼船就下不来了的感觉。
其实我做ACM似乎也是这样的一个状态，刚开始一个人做的时候并没有想过以后会做成什么样，取得什么成绩，甚至没想过会做多久。但是当和人组队之后，我就觉得上了贼船下不去了，这个时候和一个人就完全不一样了，一个队就是一个整体，最后一年就一直是这样的一种责任感驱使着我坚持完了regional。一个人最清楚的就是自己的水平到底怎么样，既然已经没有遗憾，所以那个时候我就觉得该退出了。
转回到现在，恐怕也是一种同样的感觉在驱使着我尽力做好管理员的工作，在一个地方呆久了，无论如何都会产生感情。我在ACM Group里整整呆了两年，当然最希望的就是我们学校的ACM活动能不断发扬光大。从去年11月份到现在，任内总共办了两场校赛，十二场周赛，一场省赛热身赛，七次二区讲座，不敢说每次活动我都亲力亲为，但我都已经尽力参与其中。现在我觉得，我所做的这一切，哪怕仅仅激起了大家一点点对ACM的热情，那就是有意义的。
这个学期结束后我就该卸任了，突然想起了前任管理员范神，一佳学长，FF学长，甚至是我不认识的上古神牛。我觉得他们当管理员时应该都是全心全意为ACM Group着想，对比我这么个半吊子+喜欢扯淡的人，还常常想着吃力不讨好…真是不免羞愧。
不管怎么说， 还是希望未来有更多肯努力的同学能加入到ACM Group中，将ACM活动发扬光大。让我们学校可以一直在world final中与世界一流大学一争高下，甚至冲击金奖吧。
