其实这些题除了第三题外都是可做的啊……
第一题int被乘爆，而且少讨论了一种情况
第二题摸到了正解的边，但是想来想去不敢写，最后竟然连部分分都没有
第三题完全懵比
第一题就是一个简单的贪心，非常简单，就是细节很多
直接上代码了：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> const int MAXN=105; typedef long long LL; using namespace std; struct node{LL d,m;}zd[MAXN]; LL p[MAXN]; bool cmp(node a,node b){ return a.d<b.d; } inline void Read(int &Ret){ char ch;bool flag=0; for(;ch=getchar(),ch<'0'||ch>'9';)if(ch=='-') flag=1; for(Ret=ch-'0';ch=getchar(),'0'<=ch&&ch<='9';Ret=Ret*10+ch-'0'); flag&&(Ret=-Ret); } LL N,T; int main() { scanf("%I64d",&N); LL num=0; for(int i=1;i<=N;i++) { scanf("%I64d%I64d",&zd[i].m,&zd[i].d); num+=zd[i].m;//处理出总共要搬多少砖 } sort(zd+1,zd+N+1,cmp);//按价值排序 scanf("%I64d",&T); LL ans=0; LL F=1,cnt=0; bool flag=0; for(int i=1;i<=T;i++) { scanf("%I64d",&p[i]); if(p[i]>num&&!flag) p[i]=num,flag=1; //如果时间分割点已经大于num，后面那一段已经无意义了 if(p[i]>num) continue; LL up=p[i]-p[i-1],t;//up是这段时间能搬多少砖，t保存能够搬多少第cnt种的砖 for(LL j=0;j<=up;) { if(j+zd[++cnt].m<=up)//如果第cnt种的砖能被全部搬完 { t=zd[cnt].m; j+=zd[cnt].m; ans+=t*F*zd[cnt].d; zd[cnt].m=0; } else { t=up-j; j=up+1; zd[cnt].m-=t; ans+=t*F*zd[cnt--].d; } } F++; } if(cnt!=N) { for(int i=cnt;i<=N;i++) ans+=zd[i].d*zd[i].m*F; } printf("%I64d",ans); }
第二题 这道题有一个规律，并不难发现
我们只需要将每条边两端的点的数量处理出来
取最小值乘上边的权值，相加就是答案了
程序如下（中间有段神奇的东西可以使代码在windows的环境下不爆栈）
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> const int MAXN=100005; typedef long long LL; using namespace std; struct node{int e,next;LL v;}h[MAXN*2]; int x,y,n,cnt=1,fir[MAXN]; LL z; int num[MAXN],l[MAXN],r[MAXN]; bool vis[MAXN]; inline void addedge(int t1,int t2,LL v){ h[++cnt].e=t2; h[cnt].next=fir[t1]; h[cnt].v=v; fir[t1]=cnt; } int dfs(int s){ vis[s]=1; int sum=0; for(int i=fir[s];i;i=h[i].next) if(!vis[h[i].e]) sum+=dfs(h[i].e)+1; return num[s]=sum; } int main() { /* int size=16<<20; char *p=(char*)malloc(size)+size; __asm__("movl %0, %%esp\n" :: "r"(p)); */ scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d%I64d",&x,&y,&z); addedge(x,y,z); addedge(y,x,z); } dfs(1); LL ans=0; for(int i=2;i<=cnt;i+=2) { int s=h[i].e,e=h[i^1].e; if(num[s]<num[e]) swap(s,e); LL w=min(num[e]+1,num[1]-num[e]); ans+=w*h[i].v; } printf("%I64d",ans); }
第三题众多大佬都说简单，但我楞是连部分分都没有
这道题我觉得对我很有好处，首先是标程中有个O(n)求逆元的，好厉害
然后是一些很用的思路
首先是那个O(n) 求逆元的版
LL inv(int n){ if(n==1) return 1; else return (mod-mod/n*inv(mod%n)%mod)%mod; }
给出证明：
设p=k*i+r, r<i, 1<i<p k*i+r≡0(mod p) (k*i+r)*i^(−1)*r^(−1)≡0*i^(−1)*r^(−1) (mod p) k*r^(−1)+i^(−1)≡0(mod p) i^(−1)≡-k*r^(−1) (mod p) i^(−1)≡-(p/i)*(p%i)^(−1) (mod p) A[i]=-(p/i)*A[p%i];转载于：http://blog.miskcoo.com/2014/09/linear-find-all-invert
然后就是思路：
这道题呢，让我们先来考虑n==1的情况，对于这种情况，其实可以完全等价于
一个折线的问题，算了，其实这些题解上都有，不说了，直接重点
当时我唯一没搞懂的地方就是为什么可以直接将假设n==1时的ans给n次方求出答案
其实这是不难理解的，对于子集，它是具有独立性的
怎么说呢，就是假设已经得到一个合法的情况
0 0
0 x
与另一个合法的情况
0 0
0 y
那么我们将这两个合法的方案叠加，可以得到：
0 0
0 (x,y)
仍然是合法的
于是根据乘法原理，那个n次方就不难理解了
