上周末打了一场训练赛，题目是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, , -, -}; double getScore(string r)
{
for(int i=;i<;i++)
if(r == rk[i])
return score[i]; return ;
} int main()
{ int n;
while(~scanf("%d", &n))
{
int sum = ;
double tot = ;
for(int i = ; i < n; i++)
{
int w;
string r;
cin >> w >> r;
if(r!="P" && r!="N")
{
sum += w;
tot += w * getScore(r);
}
}
if(sum == )
cout << "0.00" << endl;
else
printf("%.2f\n", tot / sum);
} return ;
}
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-;
double lim,y;
int x;
double p[];
int main()
{
while(scanf("%d%lf",&x,&y)!=EOF)
{
for(int i=; i<x; i++)
{
p[i]=;
for(int j=i; j<x; j++)
{
p[i]+=p[i]/j;
}
}
lim=y+-eps;
long long ans=;
y=;
for(int i=; i<x; i++)
{
y+=y/i;
}
if(y>lim)
{
puts("-1");
continue;
}
double now=;
for(int i=; 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 ;
}
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+;
int dp[][<<][];
char s[][];
int a[][];
int p[];
int n,m;
int c,d;
bool can(int x,int s)
{
for(int i=; i<m; i++)
{
if(((<<i)&s)&&(!a[x][i]))
return ;
}
return ;
}
void dfs(int x,int y,int num,int s,int pre)
{
if(num>d)
return;
if(y==m)
{
dp[x%][s][num]+=pre;
dp[x%][s][num]%=mod;
return;
}
if(p[y]!=-)
{
dfs(x,y+,num,s,pre);
return;
}
dfs(x,y+,num+,s,pre);
dfs(x,y+,num,s|(<<y),pre);
if(y<m-&&(p[y+]==-))
{
dfs(x,y+,num,s,pre);
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d%d%d",&n,&m,&c,&d)!=EOF)
{
memset(dp,,sizeof(dp));
dp[][][]=;
for(int i=; i<=n; i++)
{
scanf("%s",s[i]);
for(int j=; j<m; j++)
{
a[i][j]=s[i][j]=='';
}
}
for(int i=; i<=n; i++)
{
for(int j=; j<(<<m); j++)
{
for(int t=; t<=d; t++)
{
if(can(i,j))
{
memset(p,-,sizeof(p));
for(int k=; k<m; k++)
{
if(((<<k)&j)||(a[i][k]==))
{
p[k]=;
}
}
dfs(i,,t,,dp[(i-)%][j][t]);
}
}
}
memset(dp[(i-)%],,sizeof(dp[(i-)%]));
}
long long ans=;
for(int i=c;i<=d;i++)
{
ans+=dp[n%][][i];
ans%=mod;
}
printf("%I64d\n",ans);
}
return ;
}
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+;
long long dp[][][];
long long tmp[][];
int h[];
int l[];
vector<int> g[];
int n;
void dfs(int now,int pre)
{
if(now)
{
dp[now][][]=;
dp[now][][]=;
}
else
dp[now][][]=;
h[now]=l[now]=;
for(int i=; 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[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j+]+=dp[now][][+xy]*dp[to][][+j]%mod;
tmp[][+xy+j-]+=dp[now][][+xy]*dp[to][][+j]%mod;
}
}
for(int xy=- ;xy<=; xy++)
{
for(int j=; j<=; j++)
{
dp[now][j][xy+]=tmp[j][+xy]%mod;
if(dp[now][j][xy+])
{
h[now]=max(h[now],xy);
l[now]=min(l[now],xy);
}
}
}
memset(tmp,,sizeof(tmp));
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp,,sizeof(dp));
for(int i=; i<=; i++)
{
g[i].clear();
}
for(int i=; i<n-; i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
g[].push_back();
dfs(,);
long long ans=;
for(int xy=; xy<=; xy++)
{
ans+=dp[][][+xy]%mod*xy%mod;
ans%=mod;
}
printf("%I64d\n",ans);
}
return ;
}
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+;
int n;
long long a[];
long long dp[][];
long long ans[]; //适用于正负整数
template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return ; //EOF
while(c!='-'&&(c<''||c>'')) c=getchar();
sgn=(c=='-')?-:;
ret=(c=='-')?:(c-'');
while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');
ret*=sgn;
return ;
} inline void out(long long x) {
if(x>) out(x/);
putchar(x%+'');
} int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
memset(ans,,sizeof(ans));
for(int i=; i<=n; i++)
{
scanf("%I64d",a+i);
//scan_d(a[i]);
}
for(int i=; i<; i++)
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int j=; j<=n; j++)
{
for(int k=j-; k>=; 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+][]+=dp[k][];
dp[k+][]%=mod;
dp[k+][]+=dp[k][];
dp[k+][]%=mod;
}
else
{
dp[k+][]+=dp[k][];
dp[k+][]%=mod;
dp[k+][]+=dp[k][];
dp[k+][]%=mod;
}
}
}
for(int j=; j<=n; j++)
{
if(dp[j][]>=)
{
ans[j]+=(1LL<<(i))%mod*dp[j][]%mod;
ans[j]%=mod;
}
}
}
for(int i=; i<=n; i++)
{
printf("%I64d%c",ans[i],i==n?'\n':' ');
}
}
return ;
}
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[];
int main()
{
// freopen("in.txt","r",stdin);
while(scanf("%I64d%I64d%I64d",a,a+,a+)!=EOF)
{
sort(a,a+);
long long ans=;
if(a[]>=)
{
a[]-=;
a[]-=;
a[]-=;
ans=;
ans+=(a[]+a[]+a[])*;
cout<<ans<<endl;
continue;
}
if(a[]==)
{
a[]-=;
a[]-=;
a[]-=;
ans=;
if(a[])
{
a[]--;
a[]--;
ans+=;
ans+=(a[]+a[])*;
cout<<ans<<endl;
continue;
}
if(a[])
{
a[]--;
ans+=;
ans+=a[]*;
cout<<ans<<endl;
continue;
}
cout<<ans<<endl;
continue;
}
if(a[])
{
a[]--;
a[]--;
ans=;
if(a[])
{
a[]--;
a[]--;
ans+=;
ans+=(a[]+a[])*;
cout<<ans<<endl;
continue;
}
if(a[])
{ a[]--;
ans+=;
ans+=(a[])*;
cout<<ans<<endl;
continue;
}
cout<<ans<<endl;
continue;
}
if(a[]>)
{
a[]-=;
ans=;
ans+=(a[])*;
}
cout<<ans<<endl;
}
return ;
}
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-;
const int maxn = 1e5+;
const int mod = 1e6+;
int inv[mod];
int pow(int a, int n)
{
int res = ;
while (n > )
{
if (n & )
res = ((ll)res * a) % mod;
a = ((ll)a * a) % mod;
n >>= ;
}
return res;
}
void Get_inv()
{
for (int i = ; i < mod; i++)
inv[i] = pow(i, mod-);
}
int N, K, tot, head[maxn];
struct Edge
{
int to, next;
} e[maxn << ];
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] = ;
mstree[r] = ;
int maxv = ;
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[];
void update (int x, int y)
{
if (x > y)
swap(x, y);
if (ans[] > x)
ans[] = x, ans[] = y;
else if (ans[] == x && ans[] > y)
ans[] = 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 = ;
Get_mul(v, r, val[v]);
for (int i = ; 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 = ; 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 = ;
mstree[] = N;
FindGravity(v, r, siz[v]);
solve(gravity);
}
} void init()
{
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
memset(has, , sizeof(has));
gravity = tot = time = ;
mstree[] = N;
ans[] = ans[] = inf;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
/*本地扩栈、*/
int stksize = << ;
char *pointer = (char *)malloc(stksize) + stksize;
__asm__ ("movl %0,%%esp"::"r"(pointer));//64λ movq %0,%%rsp
#endif Get_inv();
while (~scanf ("%d%d", &N,&K))
{
init();
for (int i = ; i <= N; i++)
scanf ("%d", val+i);
for (int i = ; i < N-; i++)
{
int u, v;
scanf ("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
FindGravity(, , N);
solve(gravity);
if (ans[] == inf)
printf("No solution\n");
else
printf("%d %d\n", ans[], ans[]);
}
return ;
}