T1辣鸡
T1就搞得这莫不愉快。。
大致题意是给你几个矩形，矩形覆盖的点都标记上，每个矩形无重复部分，求满足(x,y)
(x+1,y+1)都标记过的点对数，范围1e9。
看起来很牛的样子，我确实也被1e9吓怕了，可是事实上这道题的处理方式就是暴力。首先有N=1的部分分，这也提示我们计算时要分成矩形内部和边界上。考虑到要相邻才行，而数据是无序的，上来先根据X1,Y1来sort一下，这样做方便暴力查找。
找的时候竖着就是X1+1==X2之时，横着有两种，因为第一关键字是X1,所以Y1不一定严格递增。那么就是i的Y1+1 ==j的Y2 或 i，j反过来。这里用的是或的关系，是因为Y1和Y2有相等的情况，并列的话会算两次;
还有一个重要的细节就是x，y和x+1,y+1;此时不会有相邻的边，但是会有一个点对。好了，就这样暴力的解决了，细节还是蛮多的。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
struct ss
{int x1,x2,y1,y2;}zxb[100001];
inline bool cmp1(ss i,ss j)
{if(i.x1==j.x1)return i.y1<j.y1;
return i.x1<j.x1;
}
signed main()
{ scanf("%lld",&n);
int mx=0,my=0;
for(int i=1;i<=n;++i)
{ int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
mx=max(mx,c);my=max(my,d);
zxb[i].x1=a,zxb[i].y1=b;zxb[i].x2=c;zxb[i].y2=d;
ans+=(d-b)*(c-a)*2;
}
sort(zxb+1,zxb+1+n,cmp1);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
{ if(zxb[i].x2+1<zxb[j].x1)break;
if(zxb[i].x2+1==zxb[j].x1)
{ int mm=min(zxb[i].y2,zxb[j].y2)-max(zxb[i].y1,zxb[j].y1);
if(mm>=0)
{ ans+=mm*2;
if(zxb[i].y2!=zxb[j].y2)++ans;
if(zxb[i].y1!=zxb[j].y1)++ans;
}
}
if(zxb[i].y2+1==zxb[j].y1 || zxb[i].y1-1==zxb[j].y2)
{ int mm=min(zxb[i].x2,zxb[j].x2)-max(zxb[i].x1,zxb[j].x1);
if(mm>=0)
{
ans+=mm*2;
if(zxb[i].x2!=zxb[j].x2)++ans;
if(zxb[i].x1!=zxb[j].x1)++ans;
}
}
if(zxb[i].x2+1==zxb[j].x1 and (zxb[i].y2+1==zxb[j].y1 or zxb[i].y1==zxb[j].y2+1))++ans;
}
cout<<ans<<endl;
}
T2模板
嗯？模板？你确定？
反正我是不信。。。
考场上我感觉数据结构很亲切，似乎是最可做的一题，于是开干。LCT 合并打了TM
俩小时，最后越打越TM像暴力，好吧，就算是暴力也有好多分数的，但是TM的tag根本就打不下去，然后上了欧拉序，in，out肯本JB加不起来，MD傻逼桶卡的难受。
2 hours later 考试过半，我还一分没拿，当场暴毙。还是老老实实打暴力。结果暴力TM忘了判重，就十分。。。。。。
部分分有一档是不需要考虑桶的，然而我直接弃掉了，根本没看见。
正解是线段树merge，比较新颖的操作是以时间为下标，然后维护操作时不用管到根怎样怎样，把操作节点的信息合并上去就好。其实好象是树套树，因为每一个节点都是一颗权值线段树。我一时间为下标是为了统计优先级，线段树干这个活要用二分，其实平衡树貌似更适合干这事。话说我也好久没打平衡树了,就当review.
具体思路，先把操作插入每个节点，然后dfs从叶子往根上进行平衡树合并，其实就是把size较小的一棵树插入size较大的树中，然后更新父亲所对应的平衡树id。这样的话我们时间就解决了，考虑个数种数。一种思路是把相同种的球时间靠前的val设为1,如果出现过,则设为0.这样是考虑时间优先,注意此处的val设为0并不是说这个点不放球,而是说放但是对ans没有贡献.这里需要在插入时判断之前有,val插成0,如果已有的时间更靠后,则需change一下,将靠后的val设为0.Q时讯问每一个点,直接输出在dfs时得到的每一个点的答案.至于桶的limit,对于平衡树查找是轻而易举的.需要注意limit查找是根据size,是球的个数,而ans是由cnt,球的种类数产生贡献的.好了,此题解决.
code
#include<bits/stdc++.h>
#define f() cout<<"fuck"<<endl
#define N 500001
using namespace std;
int head[N],n,m,k[N],now1,q,id[N],cnt,tot,ans[N],num,ans1;
struct x813x
{int to,next;
}bian[N];
struct y1111y
{int ch[2],cnt,siz,col,fa,tim,val;}t[N*40];
struct I000I
{ int root;map<int ,int >mp;
inline int size()
{return t[root].siz;}
inline bool get(int x)
{return t[t[x].fa].ch[1]==x;}
inline void update(int x)
{ t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+1;
t[x].cnt=t[t[x].ch[0]].cnt+t[t[x].ch[1]].cnt+t[x].val;
}
inline void rotate(int x)
{ int die=t[x].fa,ye=t[die].fa,hao=get(x);
t[die].ch[hao]=t[x].ch[hao^1];
t[t[die].ch[hao]].fa=die;
t[x].ch[hao^1]=die;
t[die].fa=x;t[x].fa=ye;
if(ye)t[ye].ch[t[ye].ch[1]==die]=x;
update(die);update(x);
}
inline void splay(int x)
{ for(int i;i=t[x].fa;rotate(x))
if(t[i].fa)rotate((get(i)==get(x))?i:x);
update(x);
root=x;
}
inline void insert(int tim,int col,int val)
{ int f=0,x=root;
while(x and t[x].tim!=tim)
{ f=x;
x=t[x].ch[t[x].tim<tim];
}
x=++num;
if(f)t[f].ch[t[f].tim<tim]=x;
t[x].tim=tim;t[x].col=col;t[x].fa=f;
t[x].cnt=t[x].val=val;t[x].siz=1;
splay(x);
}
inline void change(int tim)
{ int now=root;
while(now and t[now].tim!=tim)now=t[now].ch[t[now].tim<tim];
if(now)t[now].val=0;
splay(now);
}
inline bool find1(int tim,int col)
{ if(!mp[col])
{ mp[col]=tim;
return 1;
}
else
if(mp[col]>tim)
{ change(mp[col]);
mp[col]=tim;
return 1;
}
else
return 0;
}
inline int findx(int x,int limit)
{ if(!x)return 0;
if(t[t[x].ch[0]].siz>=limit)findx(t[x].ch[0],limit);
else if(t[t[x].ch[0]].siz+1>=limit)return ans1+t[t[x].ch[0]].cnt+t[x].val;
else ans1+=t[t[x].ch[0]].cnt+t[x].val,findx(t[x].ch[1],limit-t[t[x].ch[0]].siz-1);
}
inline int findval(int limit)
{ ans1=0;
if(!limit)return 0;
if(t[root].siz<=limit)return t[root].cnt;
int x=findx(root,limit);
return x;
}
}a[N];
namespace AYX
{ inline void update(int x)
{ if(!x)return;
update(t[x].ch[0]);
a[now1].insert(t[x].tim,t[x].col,a[now1].find1(t[x].tim,t[x].col));
update(t[x].ch[1]);
}
inline void dfs(int x,int fa)
{ for(int i=head[x];i;i=bian[i].next)
{ int y=bian[i].to;
if(y==fa)continue;
//f();
dfs(y,x);
if(a[id[x]].size()<a[id[y]].size())
{ now1=id[y];
update(a[id[x]].root);
id[x]=now1;
}
else
{ now1=id[x];
update(a[id[y]].root);
}
}
ans[x]=a[id[x]].findval(k[x]);
}
inline void add(int u,int v)
{ bian[++cnt].to=v;
bian[cnt].next=head[u];
head[u]=cnt;
}
inline short main()
{ scanf("%d",&n);
for(int i=1;i<n;++i)
{ int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
for(int i=1;i<=n;++i)id[i]=i,scanf("%d",&k[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{ int x,c;
scanf("%d%d",&x,&c);
a[id[x]].insert(i,c,a[id[x]].find1(i,c));
}
dfs(1,0);
scanf("%d",&q);
for(int i=1;i<=q;++i)
{ int v,x;
scanf("%d",&x);
printf("%d\n",ans[x]);
}
}
}
signed main()
{return AYX::main();}
T3大佬
这完蛋玩意,又是假期望.其实这题也不是很难,就是题面看错了.......
好吧,在来看一下,取值范围是1-m,而对应的劳累值是题目中给出的m[i]......而不是直接随机取m[i].好吧,话说题面搞错了还有十分?
正解就是算贡献,貌似是在计数,嗯,确实在计数.试想对于一个值i,他成为u最大值的方案数是多少呢?要想他是最大值,那我k天之内的取值都得在i之内,所以是ik.但是这里面有最大值不是i的情况,所以再减去(i-1)k.方案数乘上值,最后乘上总天数除以总方案数m^k即可.
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,m,k,w[1011],ans;
inline int qpow(int a,int b)
{ int base=1;
while(b)
{ if(b&1)base=base*a%mod;
a=a*a%mod;
b>>=1;
}
return base;
}
signed main()
{ scanf("%lld%lld%lld",&n,&m,&k);if(k>n){cout<<0;return 0;}
for(int i=1;i<=m;++i)
{ int s;scanf("%lld",&s);
(ans+=(qpow(i,k)-qpow(i-1,k)+mod)%mod*s%mod)%=mod;
}
printf("%lld",ans*(n-k+1)%mod*qpow(qpow(m,k),mod-2)%mod);
}
T4宝藏
状压好题,但是不知道为什么我考场上看着总想克鲁斯卡尔重构树,最后当然是完蛋的.
本题瓶颈在于那个边权上要乘的系数,也就是深度.还有他去跟谁连边,这些东西都是变量,搞得人头疼.其实可以换个思路,神魔东西不好搞,就把它扔到状态里嘛,层数不好弄,我们就让他进数组第一层,第二层是状态,表示已经连了那些边.方程已经很明显了,只需预处理出i状态变为j状态的最小值是多少.我们对于dp是不用担心后效性的,因为再二进制枚举中每一个1都覆盖过不同的情况,同样都是取min.
代码实现中要枚举子集,这里有一个巧妙的方法实现,code
#include<bits/stdc++.h>
using namespace std;
int zxb[1<<14][1<<14],dis[103][103],n,m;long long dian[111];
long long ans=0x7fffffff;
long long dp[15][1<<14];
signed main()
{ scanf("%d%d",&n,&m);
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;++i)
{ int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(dis[a][b]>c)dis[a][b]=dis[b][a]=c;
}
for(int i=1;i<=n;++i)dian[i]=(1<<(i-1));
for(int i=0;i<(1<<n);++i)
for(int j=i;j;j=(j-1)&i)
{ int temp=i^j;bool bo=0;
for(int k=n;k;--k)
{ int tin=0x3f3f3f3f;
if(temp>=dian[k])
{ tin=0x3f3f3f3f;
for(int p=1;p<=n;++p)
if((dian[p]&j)==dian[p])
tin=min(tin,dis[p][k]);
if(tin==0x3f3f3f3f){bo=1;break;}
zxb[j][i]+=tin;
temp-=dian[k];
}
}
if(bo)zxb[j][i]=0x3f3f3f3f;
}
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;++i)dp[1][dian[i]]=0;
for(int ceng=2;ceng<=n;++ceng)
for(int i=0;i<(1<<n);++i)
for(int j=i;j;j=(j-1)&i)if(zxb[j][i]!=0x3f3f3f3f)
dp[ceng][i]=(long long)min(dp[ceng-1][j]+(long long )(ceng-1)*zxb[j][i],dp[ceng][i]);
for(int i=1;i<=n;++i)ans=min(ans,dp[i][(1<<n)-1]);
printf("%lld\n",ans);
}