2018 ccpc 网络赛总结及部分题解
参加的第一场正儿八经的ACM比赛，从头到尾连开五题最终除了1004签到之外全部凉凉。总结一下，在做题策略上还是不要过于长时间一个人生怼一道题，要注重团队合作的意识，除此之外，能力还是差很多，做题量远远不够，对模型的分析和转化能力待加强。
大概就说下开了的那五题吧
链接 1001 hdu6438 Buy and Resell
题目大意：商人能在N个地方以aiai的价格买入或卖出商品，在每个地方只能做一次交易。要求最大的收益，同时最小化交易次数。(这道题比赛剩二十分钟的时候队友才给我看，突然发现以前做过一道基本差不多的题，然而加入本题要求的天数后一直调试到比赛结束，可惜了)
明白题意后，很显然的想法贪心或着dp，但是发现每一天的状态不仅要受过去和未来两个方面的影响，dp有点不合适。所以采取贪心。因为有买和卖两种情况要考虑，所以我们考虑拆点，并假设一开始每天都是买的，用优先队列存两次，当一个数两次都被pop出去后，表示该价格买入。重点要考虑买入和卖出价格相同时，忽略他们的应对措施，即用该数的编号id区分，每个数出现的次数用map维护，详情见代码。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long ll;
using namespace std;
int n,x;
ll z;
struct Info
{
int val;
int id;
bool operator<(const Info &aa) const{
if(aa.val==val)return id<aa.id;
return val<aa.val;
}
}a[100010];
priority_queue<Info> q;
map<int,int> ma;
int v[100010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int cnt=0;
z=0;
scanf("%d",&n);
ma.clear();
memset(v,0,sizeof(v));
while(!q.empty()) q.pop();
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[i].val=-x;
a[i].id=i;
}
for(int i=1;i<=n;i++){
q.push(a[i]);
q.push(a[i]);
z+=-a[i].val+q.top().val;
v[q.top().id]++;
q.pop();
}
for(int i=1;i<=n;i++){
if(v[i]==0)ma[-a[i].val]++;
else if(v[i]==2){
if(ma[-a[i].val]==0)cnt++;
else ma[-a[i].val]--;
}
}
printf("%I64d %d\n",z,2*cnt);
}
}题目大意:让你重新定义任意一对数的乘法和加法结果（输出乘法口诀表和加法口诀表），使得mp+np==(m+n)^p（p为质数），并且存在一个0<q<p使得 q^k(0<k<p)取遍1~p-1的所有值，并且该运算是封闭的（exists an integer q(0<q<p) to make the set {qk|0<k<p,k∈Z} equal to {k|0<k<p,k∈Z}.）
由于题目中给到p为质数且有幂的形式，自然想到费马小定理，即
同理
，又由题目要求可以看出，只需要在模p的意义下将加法定义成乘法，乘法为加法即可。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long ll;
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int p;
scanf("%d",&p);
for(int i=1;i<=p;i++)
{
for(int j=1;j<=p;j++)
if(j==p) printf("%d\n",(i+j-2)%p );
else printf("%d ",(i+j-2)%p);
}
for(int i=1;i<=p;i++)
{
for(int j=1;j<=p;j++)
if(j==p) printf("%d\n",(i-1)%p*(j-1)%p );
else printf("%d ",(i-1)%p*(j-1)%p);
}
}
return 0;
}题意很明显，做法也很明显，队友一个费马大定理就解决了n>2的所有情况----无解，n=0时，显然无解，n=1时，显然斜率为1的直线随便取就行，只有n=2时需要稍稍动下脑子，很明显这是一组勾股数
,把b一过去因式分解，对a判断奇偶分类讨论即可。
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e5+10;
int a,b,c;
int main()
{
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d%d",&n,&a);
if(n>2||!n) printf("-1 -1\n");
else if(n==1) printf("%d %d\n",a,2*a);
else{
if(a&1) printf("%d %d\n",(a*a-1)/2,(a*a+1)/2);
else printf("%d %d\n",(a*a)/4-1,(a*a)/4+1);
}
}
return 0;
}链接 1009 hdu6446 Tree and Permutation
这就是一道全队怼了好久不愿意放弃的题(都已经把结论猜出来了倒在dfs上，然并卵)
题目大意：给你一棵树。n(n<=1e5)个点，n-1条边。每条边有权值w。1~n 这n个数可以产生n!个全排列。对于某个全排列，比如2413 我们计算一个值，这个值为 树中2号节点到4号节点的距离+4号节点到1号节点的距离+1号节点到3号节点的距离。求所有排列的这个值的和。
首先，对于题目给出的n-1条边，我们可以这样考虑，去掉这条边后，将树分成了两部分，一部分有M个节点，另一部分有（N-M）个节点，所以我们必须在这两块中任意选择一个节点才会进过这条边，所以，有NM2中选择，然后又N！个序列所以对于E这条边，一共又2NM*（N-1）！*L的贡献。(不懂什么树上dp，写个dfs就完事了)
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
typedef long long ll;
using namespace std;
#define midf(x,y) (((x)+(y))>>1)
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
#define INF 0x3f3f3f3f
const int maxn=1e5+10;
const int mod=1e9+7;
int n,u,v,val,tot,head[maxn];
ll f[maxn],dp[maxn],ans;
struct Edge{
int to,next,w;
}edge[2*maxn];
void add(int u,int v,int val)
{
edge[tot].to=v;
edge[tot].next=head[u];
edge[tot].w=val;
head[u]=tot++;
}
void init()
{
memset(dp,0,sizeof(dp));
memset(head,-1,sizeof(head));
}
void initfac()
{
f[0]=f[1]=1;
for(int i=2;i<maxn;i++) f[i]=f[i-1]*i%mod;
}
void dfs(int u,int fa)
{
dp[u]=1;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to,w=edge[i].w;
if(v==fa) continue;
dfs(v,u);
dp[u]+=dp[v];
ans=(ans+dp[v]*(n-dp[v])%mod*w%mod)%mod;
}
}
int main()
{
//freopen("in.txt","r",stdin);
initfac();
while(~scanf("%d",&n))
{
init(),tot=1;
for(int i=1;i<=n-1;i++){
scanf("%d%d%d",&u,&v,&val);
add(u,v,val);
add(v,u,val);
}
ans=0,dfs(1,-1);
ans=ans*2%mod*f[n-1]%mod;
printf("%I64d\n",ans );
}
return 0;
}希望下次比赛能够发挥应有实力把！毕竟，Acmer之旅才正要开始！