上周末打了一场训练赛，题目是13年南京区域赛的
这场题目有好几个本来应该是我擅长的，但是可能是太久没做比赛了各种小错误代码写的也丑各种warusn trush搞得人很不爽
全场题之一的1002也没有想出来，最终只出了三题连铜牌线都没有达到，心好累
赛后又补了三道题，还是写一下题解毕竟好久都没写了
1001：
全场题，队长秒过
代码：
#include <iostream> #include <stdio.h> #include <string> using namespace std;string rk[] = {"A", "A-", "B+", "B", "B-", "C+", "C", "C-", "D", "D-", "F" , "P", "N"}; double score[] = {4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7, 1.3, 1.0, 0 , -1, -1};double getScore(string r) {for(int i=0;i<11;i++)if(r == rk[i])return score[i];return 0; }int main() {int n;while(~scanf("%d", &n)){int sum = 0;double tot = 0;for(int i = 0; i < n; i++){int w;string r;cin >> w >> r;if(r!="P" && r!="N"){sum += w;tot += w * getScore(r);}}if(sum == 0)cout << "0.00" << endl;elseprintf("%.2f\n", tot / sum);}return 0; }
1002：
题意：x，y初始都是1，给定一个目标 xn,yn，现有两种操作，求达到目标状态的最小操作数（只要最终y的整数部分等于yn即可）
操作1：y++，y+=y/x (小数除法)
操作2：x++；
分类：数学、贪心
做法：首先已知xn可求得操作2的数目，而观察操作1可知越早执行操作1 y提升的越快，所以从x=1到x=xn-1的过程中贪心的执行操作1即可 （在不达到yn+1的限制下早执行的越多越好）
代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<math.h> #include<ctype.h> using namespace std; #define MAXN 10000 const double eps=1e-2; double lim,y; int x; double p[12]; int main() {while(scanf("%d%lf",&x,&y)!=EOF){for(int i=1; i<x; i++){p[i]=1;for(int j=i; j<x; j++){p[i]+=p[i]/j;}}lim=y+1-eps;long long ans=0;y=1;for(int i=1; i<x; i++){y+=y/i;}if(y>lim){puts("-1");continue;}double now=1;for(int i=1; i<x; i++){int tmp=(floor)((lim-y)/(p[i]));ans+=tmp;y+=p[i]*tmp;ans++;}ans+=(floor)(lim-y);printf("%I64d\n",ans);}return 0; }
1003：
题意：要往一个方格构成的矩形上铺满1*1，1*2的砖，有些地方不能铺，且1*1的数量有限制，求方案数。
分类：状压dp
做法：很基础的状压dp，有人说是插头但是我觉得比变态插头简单多了，直接三维dp就好了，转移我用的是dfs。挺好理解的。
比赛的时候先被卡内存，改滚动数组又被卡常数了，后来又因为没注意边界条件导致访问非法内存warush，真是xnmbyy
代码:
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; const int mod=1e9+7; int dp[2][1<<12][22]; char s[110][12]; int a[110][12]; int p[12]; int n,m; int c,d; bool can(int x,int s) {for(int i=0; i<m; i++){if(((1<<i)&s)&&(!a[x][i]))return 0;}return 1; } void dfs(int x,int y,int num,int s,int pre) {if(num>d)return;if(y==m){dp[x%2][s][num]+=pre;dp[x%2][s][num]%=mod;return;}if(p[y]!=-1){dfs(x,y+1,num,s,pre);return;}dfs(x,y+1,num+1,s,pre);dfs(x,y+1,num,s|(1<<y),pre);if(y<m-1&&(p[y+1]==-1)){dfs(x,y+2,num,s,pre);} } int main() {//freopen("in.txt","r",stdin);while(scanf("%d%d%d%d",&n,&m,&c,&d)!=EOF){memset(dp,0,sizeof(dp));dp[0][0][0]=1;for(int i=1; i<=n; i++){scanf("%s",s[i]);for(int j=0; j<m; j++){a[i][j]=s[i][j]=='1';}}for(int i=1; i<=n; i++){for(int j=0; j<(1<<m); j++){for(int t=0; t<=d; t++){if(can(i,j)){memset(p,-1,sizeof(p));for(int k=0; k<m; k++){if(((1<<k)&j)||(a[i][k]==0)){p[k]=0;}}dfs(i,0,t,0,dp[(i-1)%2][j][t]);}}}memset(dp[(i-1)%2],0,sizeof(dp[(i-1)%2]));}long long ans=0;for(int i=c;i<=d;i++){ans+=dp[n%2][0][i];ans%=mod;}printf("%I64d\n",ans);}return 0; }
1008：
题意：把一个树上的节点随机分给三个人，然后把链接不同两人的边断掉，每个人的得分是max(0,x-y) 其中x代表他拥有的大小为奇数的连通分量个数，y是偶数
求三人得分*3^n 的期望
分类：树形dp
做法：首先yy得出三人得分和其实就是单人得分的期望的3倍，然后进行treedp算出一个的得分就好了，dp保存每个点是否取，取后当前连通分量的奇偶，以及x-y的值，
转移还是比较好想的，刚好题目要输出*3^n的 所以避免了浮点数，这点还算比较良心
hdu可惜又卡常数了，一定是我写的太挫
代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> #include<vector> using namespace std; #define MAXN 10000 const int mod=1e9+7; long long dp[310][3][800]; long long tmp[3][705]; int h[310]; int l[310]; vector<int> g[310]; int n; void dfs(int now,int pre) {if(now){dp[now][1][350]=1;dp[now][0][350]=2;}elsedp[now][0][350]=3;h[now]=l[now]=0;for(int i=0; i<g[now].size(); i++){int to=g[now][i];if(to==pre)continue;dfs(to,now);for(int xy=l[now]; xy<=h[now]; xy++){for(int j=l[to]; j<=h[to]; j++){tmp[0][350+xy+j]+=dp[now][0][350+xy]*dp[to][0][350+j]%mod;tmp[1][350+xy+j]+=dp[now][1][350+xy]*dp[to][0][350+j]%mod;tmp[1][350+xy+j]+=dp[now][1][350+xy]*dp[to][2][350+j]%mod;tmp[1][350+xy+j]+=dp[now][2][350+xy]*dp[to][1][350+j]%mod;tmp[2][350+xy+j]+=dp[now][2][350+xy]*dp[to][2][350+j]%mod;tmp[2][350+xy+j]+=dp[now][2][350+xy]*dp[to][0][350+j]%mod;tmp[2][350+xy+j]+=dp[now][1][350+xy]*dp[to][1][350+j]%mod;tmp[0][350+xy+j+1]+=dp[now][0][350+xy]*dp[to][1][350+j]%mod;tmp[0][350+xy+j-1]+=dp[now][0][350+xy]*dp[to][2][350+j]%mod;}}for(int xy=-300 ;xy<=300; xy++){for(int j=0; j<=2; j++){dp[now][j][xy+350]=tmp[j][350+xy]%mod;if(dp[now][j][xy+350]){h[now]=max(h[now],xy);l[now]=min(l[now],xy);}}}memset(tmp,0,sizeof(tmp));} } int main() {while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));for(int i=0; i<=300; i++){g[i].clear();}for(int i=0; i<n-1; i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}g[0].push_back(1);dfs(0,0);long long ans=0;for(int xy=0; xy<=300; xy++){ans+=dp[0][0][350+xy]%mod*xy%mod;ans%=mod;}printf("%I64d\n",ans);}return 0; }
1009：
题意：有n个数，对于k=1~n，求所有c(n,k)种组合分别异或之后的和
分类：dp
做法：按二进制展开，对每一位进行一个n^2的dp求出所有组合中当前位为1的有多少个，加入答案即可，然后这题我又被卡啦= =dp数组降了一维勉强才过
代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; const int mod=1e6+3; int n; long long a[1010]; long long dp[1010][2]; long long ans[1010];//适用于正负整数 template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0; //EOFwhile(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1; }inline void out(long long x) {if(x>9) out(x/10);putchar(x%10+'0'); }int main() {//freopen("in.txt","r",stdin);while(scanf("%d",&n)!=EOF){memset(ans,0,sizeof(ans));for(int i=1; i<=n; i++){scanf("%I64d",a+i);//scan_d(a[i]); }for(int i=0; i<63; i++){memset(dp,0,sizeof(dp));dp[0][0]=1;for(int j=1; j<=n; j++){for(int k=j-1; k>=0; k--){/*dp[j][k][0]+=dp[j-1][k][0];dp[j][k][0]%=mod;dp[j][k][1]+=dp[j-1][k][1];dp[j][k][1]%=mod;*/if(a[j]&(1LL<<i)){dp[k+1][1]+=dp[k][0];dp[k+1][1]%=mod;dp[k+1][0]+=dp[k][1];dp[k+1][0]%=mod;}else{dp[k+1][1]+=dp[k][1];dp[k+1][1]%=mod;dp[k+1][0]+=dp[k][0];dp[k+1][0]%=mod;}}}for(int j=1; j<=n; j++){if(dp[j][1]>=1){ans[j]+=(1LL<<(i))%mod*dp[j][1]%mod;ans[j]%=mod;}}}for(int i=1; i<=n; i++){printf("%I64d%c",ans[i],i==n?'\n':' ');}}return 0; }
1010：
题意：有三种颜色的小球（给定数量），每放一个球的得分等于前面和后面不同的颜色数
分类：贪心
做法：贪心，先尽量在前后多放不同颜色的球，剩下的填在中间即可，坑点是好多特判，容易忘某个细节
代码：
#include <iostream> #include <stdio.h> #include<string.h> #include<algorithm> #include<string> #include<ctype.h> using namespace std; #define MAXN 10000 long long a[3]; int main() {// freopen("in.txt","r",stdin);while(scanf("%I64d%I64d%I64d",a,a+1,a+2)!=EOF){sort(a,a+3);long long ans=0;if(a[0]>=2){a[0]-=2;a[1]-=2;a[2]-=2;ans=15;ans+=(a[2]+a[1]+a[0])*6;cout<<ans<<endl;continue;}if(a[0]==1){a[0]-=1;a[1]-=1;a[2]-=1;ans=3;if(a[1]){a[1]--;a[2]--;ans+=7;ans+=(a[1]+a[2])*5;cout<<ans<<endl;continue;}if(a[2]){a[2]--;ans+=3;ans+=a[2]*4;cout<<ans<<endl;continue;}cout<<ans<<endl;continue;}if(a[1]){a[1]--;a[2]--;ans=1;if(a[1]){a[1]--;a[2]--;ans+=5;ans+=(a[1]+a[2])*4;cout<<ans<<endl;continue;}if(a[2]){a[2]--;ans+=2;ans+=(a[2])*3;cout<<ans<<endl;continue;}cout<<ans<<endl;continue;}if(a[2]>1){a[2]-=2;ans=1;ans+=(a[2])*2;}cout<<ans<<endl;}return 0; }
1011：
题意：N个点的树，，每个点对应一个权值，，找出a 到b路径上吧权值的乘积%mod== K 的点对。。如果有多个输出字典序最小的那个。。。
分别是 求重心 然后分治，，查询的时候要 用到时间戳。。同时要预处理出逆元。。
(x*y) %mod == K ,,那么x = K*inv[y]%mod;
代码：
#include <set> #include <map> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") typedef unsigned long long ull; typedef long long ll; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 1e5+10; const int mod = 1e6+3; int inv[mod]; int pow(int a, int n) {int res = 1;while (n > 0){if (n & 1)res = ((ll)res * a) % mod;a = ((ll)a * a) % mod;n >>= 1;}return res; } void Get_inv() {for (int i = 0; i < mod; i++)inv[i] = pow(i, mod-2); } int N, K, tot, head[maxn]; struct Edge {int to, next; } e[maxn << 1]; void add_edge(int x, int y) {e[tot].to = y;e[tot].next = head[x];head[x] = tot++; } bool vis[maxn]; int siz[maxn], mstree[maxn], gravity; void FindGravity(int r, int father, int cnt) {siz[r] = 1;mstree[r] = 0;int maxv = 0;for (int i = head[r]; ~i ; i = e[i].next){int v = e[i].to;if (vis[v] == true || v == father)continue;FindGravity(v, r, cnt);siz[r] += siz[v];mstree[r] = max(mstree[r], siz[v]);}mstree[r] = max(mstree[r], cnt - siz[r]);if (mstree[gravity] > mstree[r])gravity = r; }int top, S[maxn], idx[maxn], has[mod], has_idx[mod], val[maxn]; void Get_mul(int r, int father, int d) {S[top] = d % mod;idx[top++] = r;for (int i = head[r]; ~i; i = e[i].next){int v = e[i].to;if (v == father || vis[v] == true)continue;Get_mul(v, r, (ll)d * val[v]%mod);} } int ans[2]; void update (int x, int y) {if (x > y)swap(x, y);if (ans[0] > x)ans[0] = x, ans[1] = y;else if (ans[0] == x && ans[1] > y)ans[1] = y; } int time; //时间戳 void update_hash(int value, int p) {if (has[value] == time) //时间戳判断是否在同一深度的递归has_idx[value] = min(has_idx[value], p);else{has[value] = time;has_idx[value] = p;} } void solve (int r) {time++;vis[r] = true;for (int j = head[r]; ~j; j = e[j].next){int v = e[j].to;if (vis[v] == true)continue;top = 0;Get_mul(v, r, val[v]);for (int i = 0; i < top; i++){if ((ll)S[i]*val[r]%mod == K)update(idx[i], r);int tmp = (ll)K *inv[(ll)S[i]*val[r]%mod]%mod;if (has[tmp] == time)update(has_idx[tmp], idx[i]);}for (int i = 0; i < top; i++){update_hash(S[i],idx[i]);}}for (int i = head[r]; ~i; i = e[i].next){int v = e[i].to;if (vis[v] == true)continue;gravity = 0;mstree[0] = N;FindGravity(v, r, siz[v]);solve(gravity);} }void init() {memset(head, -1, sizeof(head));memset(vis, false, sizeof(vis));memset(has, 0, sizeof(has));gravity = tot = time = 0;mstree[0] = N;ans[0] = ans[1] = inf; } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);/*本地扩栈、*/int stksize = 256 << 20;char *pointer = (char *)malloc(stksize) + stksize;__asm__ ("movl %0,%%esp"::"r"(pointer));//64λ movq %0,%%rsp #endifGet_inv();while (~scanf ("%d%d", &N,&K)){init();for (int i = 1; i <= N; i++)scanf ("%d", val+i);for (int i = 0; i < N-1; i++){int u, v;scanf ("%d%d", &u, &v);add_edge(u, v);add_edge(v, u);}FindGravity(1, 0, N);solve(gravity);if (ans[0] == inf)printf("No solution\n");elseprintf("%d %d\n", ans[0], ans[1]);}return 0; }
