隔膜
【问题描述】
steam 夏季大促销来啦，azui 大爷最近在 steam 上买了 1mol 的游
戏。一天他突然发现了一个搬砖的游戏：有 N 种砖头，每种砖头有 mi 个，每一个的价值为 di。每一个单位时间你必须搬一块砖，到无砖可搬为止。有一个得分系数 F，初始时为 1。搬一块砖的得分为当时的得分系数 F*di。有 T 个时间分割点。每过一个时间分割点，F 会自己加一。例如在时间 pi 的得分为 i*di，而在时间 pi+1 的得分为(i+1)*di。azui 大爷觉得这个游戏 too simple，不想去玩，于是让你去帮他上分，希望你能告诉他每局游戏的最大的分。你一定知道这么简单的题目怎么做，快帮帮 azui 大爷吧。
【输入格式】
第一行一个数 N。接下来的 N 行，每行两个数，表示 mi 和 di。之后的一行一个数 T。接下来的一行 T 个数，pi。
【样例输入 1】
2
3 8
5 10
1
20
【样例输出 1】
74
【样例输入 2】
1
1 1000
1
1
【样例输出 2】
1000
【数据范围】
对于 30%的数据，
1<=N<=10
对于 100%的数据，
1<=N<=100
1<=mi<=109
0<=di<=1000
1<=t<=1001<=p2<p3<…<pt<=1012
题解：按d排序。
成绩：AC
分析：水题。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N=100+10; struct node{ long long num,val; bool operator < (const node &x)const{ return val<x.val; } }arr[N]; int n,T,now=1; long long p,f,ans,res; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld %lld",&arr[i].num,&arr[i].val); sort(arr+1,arr+n+1); scanf("%d",&T); while(T--){ scanf("%lld",&p); f++; for(;now<=n;now++){ res+=arr[now].num; ans+=arr[now].num*arr[now].val*f; if(res>=p) break ; } if(res>p){ arr[now].num=res-p;res=p; ans-=arr[now].num*arr[now].val*f; } else now++; } for(;now<=n;now++) ans+=arr[now].num*arr[now].val*(f+1); printf("%lld\n",ans); }快递配对
【问题描述】
azui 大爷厌倦了每天在家颓废的生活，于是开始打工送快递。Jeremy 同学不想让 azui 大爷太轻松，于是想让他送快递的路程尽可能的长。一句话来说就是：给出一棵 n 个点的树，将这 n 个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。
【输入格式】
一个数 n（1<=n<=100,000,n 保证为偶数）接下来 n-1 行每行三个数 x,y,z 表示有一条长度为 z 的边连接 x 和y（0<=z<=1,000,000,000）
【输出格式】
一个数表示答案。
【样例输入】
6
1 2 1
1 3 1
1 4 1
3 5 1
4 6 1
题解：找树的重心，让每一条路都经过树的重心。因为假设树的根是确定的，最佳方案一定是每个节点都越过根去找配对节点，因为要让每个节点越过根，去掉根后子树一定要尽量平均，即树的重心。
成绩：0
分析：文件输入输出没有打.in和.out（被自己zz掉/(ㄒoㄒ)/~~），考试时想到了平均，但树的重心的概念完全忘了( ˇˍˇ )，就乱搞了一个点作根。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<stack> #include<algorithm> #include<vector> using namespace std; const int N=100000+10; const int inf=0x3f3f3f3f; void getint(int&son){ char c;int flag=1;son=0; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9'){son=son*10+c-48;c=getchar();} son*=flag; } struct bian{ int v,w,next; }arr[N<<1]; int n,a,b,cnt,s,t,Min=inf,fir[N],dp[N],son[N]; long long w,dis[N],ans; bool vis[N]; void link(int a,int b,int w){ arr[++cnt].v=a,arr[cnt].w=w; arr[cnt].next=fir[b],fir[b]=cnt; } void work(int x,int pre){ son[x]=1; for(int i=fir[x];i;i=arr[i].next) if(arr[i].v!=pre) work(arr[i].v,x),son[x]+=son[arr[i].v]; } void dfs(int x,int pre){ for(int i=fir[x];i;i=arr[i].next) if(arr[i].v!=pre) dfs(arr[i].v,x),dp[x]=max(dp[x],son[arr[i].v]); dp[x]=max(dp[x],n-son[x]); } void Dfs(int x){ vis[x]=1; for(int i=fir[x];i;i=arr[i].next) if(!vis[arr[i].v]){ dis[arr[i].v]=dis[x]+arr[i].w; Dfs(arr[i].v); } } int main(){ //freopen("pairing.in","r",stdin); //freopen("pairing.out","w",stdout); getint(n); for(int i=1;i<n;i++){ scanf("%d %d %lld",&s,&t,&w); link(s,t,w),link(t,s,w); } work(1,-1),dfs(1,-1); for(int i=1;i<=n;i++) Min=min(Min,dp[i]); for(int i=1;i<=n;i++) if(dp[i]==Min){ Dfs(i);break ; } for(int i=1;i<=n;i++) ans+=dis[i]; printf("%lld\n",ans); }【问题描述】
azui大爷在quack大爷的带领下开始玩集合了，可是他太懒了，不想做quack大爷布置的作业题，便拿来给你做了：
S 集合中有n个不同的元素，我们从1-n标号。考虑S 的子集Si,j，将这些子集排成一个r行c列矩阵的样子。
其中第一行为S1,1,S1,2,…,S1,c，第二行为S2,1,S2,2,..,S2,c一直到第r行为Sr,1, Sr,2,…, Sr,c。
这些集合还满足对于在一行中左右相邻的两个集右，左侧是右侧
的子集，即Si,j∈Si,j+1。
这些集合还满足对于在一列中上下相邻的两个集合，上方是下方
的子集，即Si,j∈Si+1,j。
问对于S 的全部子集，有多少可能的情况排成上述的矩阵（每个子集可以重复使用），结果模109 +7 输出。
你一定知道这么简单的题目怎么做，快帮帮azui大爷吧。
【输入格式】
一行三个数n,r,c.
【输出格式】
一个数表示答案。
【样例输入】
1 2 2
【样例输出】
6
【样例解释】
1
2
3
4
如上图标号后，有：1是2和3的子集，1，2，3都是4的子集。
用0表示空集，1表示元素1，从左到右是1、2、3、4的话，有以下6种情况
0000 0001 0011 0101 0111 1111
【数据范围】
对于10%的数据，r*c*n <= 16
对于20%的数据，r*c <= 16, n <= 100
对于另20%的数据，r=1, c<=1000000
对于另10%的数据，n=1
对于100%的数据，r, c <= 1000000, n <= 10^9s
题解：把集合中每个数分开考虑，最后再把n=1时的答案n次方（简直不敢相信考场上就差这一步，然而n=1只有一个点%>_<%），考虑只填0和x，那x一定在矩阵的右下部分，就可以吧问题转换为从左上到右下一共有多少种走法（一共走r+c步，c步向下 => C(n,m) ）。
成绩：0
分析：这次的文件输入输出不光没有打in和out还顺手注释掉了。。。但改过来也只有n=1的10分，主要是思考时看到特殊数据一直在人为地强化它的特殊性，半暴力半玄学地把式子写出来后n一变就懵掉（时间不够又很慌qnq）。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<vector> using namespace std; const int N=100+10; const long long mod=1e9+7LL; int n,r,c,ans,map[N][N]; int Max(int a,int b,int c){ return max(a,max(b,c)); } void dfs(int x,int y){ int pos=c*(x-1)+y; if(pos>=r*c+1){ ans++;return ; } for(int i=Max(1,map[x-1][y],map[x][y-1]);i<=n;i++){ map[x][y]=i; if(y<c) dfs(x,y+1); else dfs(x+1,1); } } void gcd(long long a,long long b,long long &x,long long &y){ if(!b) x=1,y=0; else gcd(b,a%b,y,x),y-=a/b*x; } int inv(int n) { if(n == 1) return 1; return (long long)(mod-mod/n)*inv(mod%n)%mod; } long long cal(long long n,long long m){ if(m>n-m) m=n-m; long long res=1,x; for(int i=1;i<=m;i++){ res=(res*(n-i+1))%mod; x=inv(i); while(x<0) x+=mod; res=(res*x)%mod; } return res; } long long qpow(long long tmp,int p){ long long res=1LL; while(p){ if(p&1) res=(res*tmp)%mod; p>>=1,tmp=(tmp*tmp)%mod; } return res; } int main(){ scanf("%d %d %d",&n,&r,&c); printf("%lld\n",qpow(cal(r+c,c),n)); return 0; } /* 1 2 2 */总结：感觉开发了自己的潜能。。（一场考试第一次两次文件错误O__O"…），我记得交卷前检查了的( ⊙ o ⊙ )，然而没看出来，错了之后又看了一遍，还是没看出来%>_<%。很多以前学过的东西忘了（树的重心o(╯□╰)o）各种失误也挺多的。。/(ㄒoㄒ)/~~，（果然洛谷说我今天大凶还忌参加模拟赛TAT）衷心期待明天不要炸得这么难看o@_@o 2333333333333333333333333333333333333333333333333333333333
