20190710 test

九月 05, 2021

20190710的test

T1

Desctription

传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以小明要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。小明装备了一个捕网，用来捕捉N组排成一行的蛇（1≤N≤400）。小明必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当小明抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。

一个大小为s的捕网意味着小明可以抓住任意包含g条的一组蛇，其中g≤s。然而，每当小明用大小为s的捕网抓住了一组g条蛇，就意味着浪费了s−g的空间。小明可以任意设定捕网的初始大小，并且她可以改变K次捕网大小（1≤K<N）。

请告诉小明她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

Input

输入的第一行包含N和K。第二行包含N个整数$a_1$,…,$a_N$，其中$a_i$（0≤$a_i$≤10^6）为第i组蛇的数量

Output

输出一个整数，为小明抓住所有蛇的总浪费空间的最小值。

Anlysis

这一道题一眼就可已看出来是在考$dp$,那么问题就在于如何来设计方程了,考试的时候我设计了一个三维的状态，接着循环写了四层，然后不负众望，$TLE$了。（而$WYXdalao$轻松$AC$）

然后重新来看，设$f[i][j]$代表第$i$个时候，用了$j$个袋子时最少浪费了多少，我们提前预处理出一个前缀和，用来获取区间内蛇的数量，因为要放下所有的蛇，所以说数量要选择最大那一个来减。

Codes

#include<bits/stdc++.h>
#define maxn 405
#define inf 0x3f3f3f3f
using namespace std;

int N,K;
int f[maxn][maxn];
int a[maxn],mxn[maxn][maxn]; 
int sum[maxn];

int main(){
	scanf("%d%d",&N,&K);
	memset(f,0x3f,sizeof(f));
	for(register int i=1;i<=N;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	//边界
	K++;//因为j要减1,所以避免负数 
	f[0][0]=0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=min(K,i);j++){
			int mxn=a[i];
			for(int k=i-1;k>=0;k--){
				f[i][j]=min(f[i][j],f[k][j-1]+mxn*(i-k)-(sum[i]-sum[k]));
				mxn=max(mxn,a[k]);
			}
		}
	}
	int ans=inf;
	for(int i=0;i<=K;i++){
		ans=min(ans,f[N][i]);
	}
	printf("%d",ans);
	return 0;
}

T2

Desctription

小明喜欢养宠物，想要将编号为1…N的N只宠物（N≤7500）分为非空的K组（2≤K≤N），使得任意两只来自不同组的宠物都需要走一定的距离才能相遇。宠物x和宠物y（其中1≤x<y≤N）愿意为了见面走 ($2019201913x$+$2019201949y$) mod $2019201997$英里。给定一个将N只宠物分为K个非空小组的分组方案，令M为任意两头来自不同组的宠物愿意为了见面行走的英里数的最小值。为了测试宠物们相互之间的忠诚度，小明想要将N头宠物以最佳的方式分为K组，使得M尽可能大

Input

输入仅有一行，包含N和K，用空格分隔。

Output

输出最优的M。

Anlysis

考试的时候我没有想到可以来找规律!!!
$$
(2019201913x+2019201949y)\mod 2019201997\\
=(-84x-48y)\mod 2019201997
$$
所以$y=N $,$x=K-1$时最大

Codes

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N,K;
	scanf("%d%d",&N,&K);
	printf("%d",-84*(K-1)-48*N+2019201997);
	return 0;
}

T3

Desctription

设T 为一棵有根树，我们做如下的定义：

• 设a和b为T 中的两个不同节点。如果a是b的祖先，那么称“a比b不知道

高明到哪里去了”。

• 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定

常数x，那么称“a 与b 谈笑风生”。

给定一棵n个节点的有根树T，节点的编号为1 到 n，根节点为1号节点。你需

要回答q 个询问，询问给定两个整数p和k，问有多少个有序三元组(a;b;c)满足：

a、b和 c为 T 中三个不同的点，且 a为p 号节点；

a和b 都比 c不知道高明到哪里去了；

a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。

Input

输入文件的第一行含有两个正整数n和q，分别代表有根树的点数与询问的个数。接下来n – 1行，每行描述一条树上的边。每行含有两个整数u和v，代表在节点u和v之间有一条边。

接下来q行，每行描述一个操作。第i行含有两个整数，分别表示第i个询问的p和k。。

Output

输出 q 行，每行对应一个询问，代表询问的答案。

Anlysis

这一道题，首先要明白，要分两种情况

$b$是$a$的祖先，这种情况比较简单，可以根据乘法原理，在$O(1)$内得到答案
$b$是$a$的子孙，这种情况就不好求了，要用主席树来做，选择以深度为下标，$size$作为维护的值进行修改。还要用到$dfs$序，一个节点和他的子树的序号是一个连续的区间，这样来进行查询

考试的时候，当然就是没有做出来了

Codes

#include<bits/stdc++.h>
#define maxn 600300
#define Int64 long long
using namespace std;


int N,Q;
int siz[maxn],dep[maxn],fa[maxn];
int head[maxn],to[maxn],nxt[maxn],tot=0;
int cnt=0,s=0;
int dfn[maxn],Root[maxn];
int maxdep=0;
struct nde{
    int lch,rch;
    Int64 data;
}sgt[maxn*20];

inline void read(int &x){
    x=0;int sign=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
    x*=sign; 
}

inline void add(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

void dfs(int u){
    siz[u]=1;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!siz[v]){
            dep[v]=dep[u]+1;
            maxdep=max(dep[v],maxdep);
            fa[v]=u;
            dfs(v);
            siz[u]+=siz[v];
        }
    }
}

void insert(int &p,int l,int r,Int64 val,int pur){
    sgt[++s]=sgt[p];
    p=s;
    sgt[p].data+=val;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(mid>=pur)insert(sgt[p].lch,l,mid,val,pur);
    else insert(sgt[p].rch,mid+1,r,val,pur);
}

Int64 query(int ver1,int ver2,int l,int r,int x,int y){
    if(l==x&&r==y)return sgt[ver2].data-sgt[ver1].data;
    int mid=(l+r)>>1;
    if(mid>=y)return query(sgt[ver1].lch,sgt[ver2].lch,l,mid,x,y);
    else if(mid<x) return query(sgt[ver1].rch,sgt[ver2].rch,mid+1,r,x,y);
    else return query(sgt[ver1].lch,sgt[ver2].lch,l,mid,x,mid)+query(sgt[ver1].rch,sgt[ver2].rch,mid+1,r,mid+1,y);
} 

void dfs_(int u){
    dfn[u]=++cnt;
    Root[cnt]=Root[cnt-1];//insert里面会给这个root赋值的 
    insert(Root[cnt],1,maxdep,(Int64)siz[u]-1,dep[u]);
    //因为是以dep作为下标来的，所以是1-maxdep
    //然后每一个深度相同的插入可以当作对这个的修改。 
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(v!=fa[u])dfs_(v);
    }
}

int main(){
    //freopen("talk.in","r",stdin);
    //freopen("talk.out","w",stdout);
    read(N);read(Q);
    for(int i=1;i<=N-1;i++){
        int x,y;
        read(x);read(y);
        add(x,y);add(y,x);
    } 
    dep[1]=1;
    dfs(1);
    dfs_(1);
    while(Q--){
        int p,k;
        read(p);read(k);
        if(dep[p]==maxdep){printf("0\n");continue;}
        Int64 ans=0;
        ans+=(long long)(min(k,dep[p]-1))*(siz[p]-1);
        int l=dfn[p]-1,r=dfn[p]+siz[p]-1;
        ans+=query(Root[l],Root[r],1,maxdep,dep[p]+1,min(maxdep,dep[p]+k));
        printf("%lld\n",ans); 
    }
    return 0;
}

查看评论

1. 20190710的test