T1
难过，以为这道题要卡快读，用的(fread)，然而没有读负数调了一下午
这道题的思路很简单。考虑是否打御符，如果要打御符就打完，不然不如不打。
然后就分两种情况：是否打御符。
如果不打御符 很简单，一直将自己手上牌的最大值和兵符的最小值进行做差，如果差值小于零，(break)就可以了。
如果打御符，打完了我们可以选择直接攻击对面的玩家。但是！如果兵符有小于0的，当前的最大值与对面的小于零的兵符做差，肯定比直接打划算fuck.直接攻击玩家相当于与等于零的兵符做差，这样讲可能好理解一点。 然后因为这个细节，基本全挂了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const LL maxn=1e6+100;
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node{
LL power,num;
}a1[maxn],a2[maxn],b1[maxn],b2[maxn],c1[maxn],c2[maxn];
LL n,m1,m2,ans;
LL work1(){
LL i=n,sum=0;
for(LL j=1;j<=m2;j++){
while(i && a1[i].power>=c1[j].power && a1[i].num<c1[j].num){
sum+=(a1[i].power-c1[j].power)*a1[i].num;
c1[j].num-=a1[i].num;a1[i].num=0;i--;
}
if(!i || a1[i].power<c1[j].power) break;
sum+=(a1[i].power-c1[j].power)*c1[j].num;
a1[i].num-=c1[j].num;c1[j].num=0;
}
return sum;
}
LL work2(){
LL i=1,sum=0;bool flag=false;
for(LL j=1;j<=m1;j++){
while(i<n && a1[i].power<b1[j].power) i++;
while(i<n && a1[i].power>=b1[j].power && a1[i].num<b1[j].num)
b1[j].num-=a1[i].num,a1[i].num=0,i++;
if(a1[i].num<b1[j].num){flag=true; break;}
a1[i].num-=b1[j].num;b1[j].num=0;
if(i==n && a1[i].num==0){flag=true;break;}
}
i=n;
for(LL j=1;j<=m2;j++){
if(c1[j].power>=0) break;
while(i && a1[i].power>=c1[j].power && a1[i].num<c1[j].num){
sum+=(a1[i].power-c1[j].power)*a1[i].num;
c1[j].num-=a1[i].num;a1[i].num=0;i--;
}
if(!i || a1[i].power<c1[j].power) break;
sum+=(a1[i].power-c1[j].power)*c1[j].num;
a1[i].num-=c1[j].num;c1[j].num=0;
}
if(!flag) for(LL j=1;j<=n;j++) if(a1[j].power>0) sum+=a1[j].power*a1[j].num;
return sum;
}
inline bool cmpl(node x,node y){return x.power<y.power;}
int main(){
freopen("panwang6.in","r",stdin);
freopen("panwangown.out","w",stdout);
n=read();m1=read();m2=read();
for(LL i=1;i<=n;i++) a1[i].power=read(),a1[i].num=read();
for(LL i=1;i<=m1;i++) b1[i].power=read(),b1[i].num=read();
for(LL i=1;i<=m2;i++) c1[i].power=read(),c1[i].num=read();
sort(a1+1,a1+1+n,cmpl);sort(b1+1,b1+1+m1,cmpl);sort(c1+1,c1+1+m2,cmpl);
for(LL i=1;i<=n;i++) a2[i]=a1[i];
for(LL i=1;i<=m1;i++) b2[i]=b1[i];
for(LL i=1;i<=m2;i++) c2[i]=c1[i];
ans=work1();swap(a1,a2);swap(b1,b2);swap(c1,c2);
ans=max(ans,work2());
printf("%lld",ans);
return 0;
}
难过
T2
一道好题。首先对于一个图来说，如果没有对其颜色的限制，那么这个图的路径集合最小显然为其最小生成树。而如果当前的期望路径和(X<sum) 显然无解 ；如果(X<sum) 首先需要知道一个性质：满足条件的MST一定与原图的MST最多相差一条边。这个性质很显然：如果有两条边与原图不同，那么当前情况肯定没有改变一条边优秀（这里的优秀指的是权值和小）
因此可以这样想：
我们枚举最小生成树边，强制加入然后算当前最小生成树，如果当前最小生成树的权值==X 显然这是合法的边 令equ为这种情况的边的数量。如果当前最小生成树的权值(<x) 显然这不是合法的边 令les为这种情况的边的数量。 显然如果原图的最小生成树如果(sum==x) 那么（不存在les） 因此满足条件的图的个数为(2^m-2*2^{m-n+1-equ}) 解释一下： 如果要使得当前的图合法 必须让至少有一条(equ)集合中的边的编号与原图最小生成树的边的编号不相同，那么显然不合法的图即为所有(equ)集合中的边编号全部都和原图最小生成树的编号相同 (2^m)表示总的情况，那么显然减去不合法的情况就是合法的情况，而不合法的情况数即为原最小生成树(n-1)条边和(equ)边编号相同，其他边任意取的方案数。注意(*2)是因为原最小生成树和(equ)边有两种编号可以取。
如果原图的最小生成树的权值(sum<x) 显然如果加上了在(les)集合里面的边，那么当前的最小生成树一定为加入的les集合里面的边和原图除了能删掉的最大边 这个时候是非法的 因为其权值(!=x) 因此我们需要令这les条边全部都与最小生成树编号相同，这样他才没有影响。因此这个时候的式子为(2*(2^{m-n+1-les}-2^{m-n+1-les-equ})) 前面一项为总方案数：因为当前加入了限制条件“必须使得les集合里面的边全部与原图最小生成树里的边的编号相同，所以这个时候的总方案数不再是(2^m) 后面一项与上一个式子类似。大概就是这样的QAQ
真的好难 我炸了 原地爆炸 旋转爆炸 360°无死角爆炸
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int t,n,m,fir[maxn],nxt[maxn<<1],to[maxn<<1],val[maxn<<1],tot;//此处邻接表存储最小生成树
int f[maxn],fa[maxn][25],maxx[maxn][25],sum,k,X,dep[maxn];
struct node{
int x,y,val,flag;
}e[maxn];
inline bool cmpl(node a,node b){
return a.val<b.val;
}
int get(int x){
if(x==f[x]) return x;
f[x]=get(f[x]);
return f[x];
}
void add(int x,int y,int z){
nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;val[tot]=z;
nxt[++tot]=fir[y];fir[y]=tot;to[tot]=x;val[tot]=z;
}
void dfs(int x){
for(int i=0;i<=20;i++)
fa[x][i+1]=fa[fa[x][i]][i];
for(int i=0;i<=20;i++)
maxx[x][i+1]=max(maxx[x][i],maxx[fa[x][i]][i]);
for(int i=fir[x];i;i=nxt[i]){
int y=to[i];if(y==fa[x][0]) continue;
fa[y][0]=x;dep[y]=dep[x]+1;
maxx[y][0]=val[i];dfs(y);
}
}
int query(int x,int y){
int shawn=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=21;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
shawn=max(shawn,maxx[x][i]);
x=fa[x][i];
}
}
if(x==y) return shawn;
for(int i=21;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
shawn=max(shawn,max(maxx[x][i],maxx[y][i]));
x=fa[x][i];y=fa[y][i];
}
}
return max(shawn,max(maxx[x][0],maxx[y][0]));
}
int ksm(int x,int y){
int tot=1;
while(y){
if(y&1) tot=(tot*x)%mod;
x=x*x%mod;y>>=1;
}
return tot%mod;
}
signed main(){
freopen("4.in","r",stdin);
t=read();
while(t--){
memset(fir,0,sizeof(fir));
memset(fa,0,sizeof(fa));
memset(dep,0,sizeof(dep));
memset(maxx,0,sizeof(maxx));
n=read();m=read();X=read();
for(int i=1;i<=m;i++){
e[i].x=read();e[i].y=read();e[i].val=read();e[i].flag=0;
}
sort(e+1,e+1+m,cmpl);
k=0;sum=0;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1,x,y,fx,fy;i<=m;i++){
x=e[i].x;y=e[i].y;
fx=get(x);fy=get(y);
if(fx!=fy){
f[fx]=fy;sum+=e[i].val;k++;
e[i].flag=1;
add(x,y,e[i].val);
}
if(k==n-1) break;
}
dfs(1);int now,equ=0,les=0;
for(int i=1;i<=m;i++){
if(!e[i].flag){
now=sum+e[i].val-query(e[i].x,e[i].y);
if(now==X) equ++;
else if(now<X)les++;
}
}
if(X==sum){
printf("%lld
",((ksm(2,m)-2*ksm(2,m-n+1-equ))%mod+mod)%mod);
}
else{
printf("%lld
",(2*(ksm(2,m-n+1-les)-ksm(2,m-n+1-les-equ))%mod)%mod);
}
}
return 0;
}
T3
咕咕咕
我真棒