2022“杭电杯”中国大学生算法设计超级联赛（6）

Maex 

有一棵以1为根节点的树，给每个节点赋一个值，从0开始到n-1，定义函数b[i]是以i为根节点的子树的MEX值，求从1~n每个b[i]值最大的和，MEX是在一个集合中没有出现过的最小的自然数。

思路：我们可以知道，最后b[1]一定是n，而怎样最大化其他节点的b值呢？从0开始辅助，我们可以很显然的知道0从最深的数的节点位置开始赋值一定是最优的，这样最深的这一棵树种每个节点的b值是它的子树的大小。这样考虑会发现，这个题的实质是求每个节点子树的大小，从第一个节点开始，每次加子树最大的那个节点，一直向下走即可。

AC Code：

#include 
 
typedef long long ll;
const int N=5e5+5;
int t,n;
std::vector<int>vec[N];
ll ans;
ll deep[N];
bool vis[N];
 
void getdeep(int u){
	vis[u]=true;
	int len=vec[u].size();
	if(len==1&&u!=1){
		deep[u]=1;
		return;
	}
	for(int i=0;i
		int v=vec[u][i];
		if(!vis[v]){
			getdeep(v);
			deep[u]+=deep[v];
		}
	}
	deep[u]++;
}
 
void getans(int u,ll tmp){
	vis[u]=true;
	int len=vec[u].size();
	if(len==1&&u!=1){
		ans=std::max(ans,tmp+deep[u]);
		return;
	}
	for(int i=0;i
		int v=vec[u][i];
		if(!vis[v]){
			getans(v,tmp+deep[u]);
		}
	}
}
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		for(int i=1;i<=n;i++){
			vec[i].clear();
			vis[i]=false,deep[i]=0;
		}
		for(int i=1;i
			int u,v;
			std::cin>>u>>v;
			vec[u].push_back(v);
			vec[v].push_back(u);
		}
		getdeep(1);
		for(int i=1;i<=n;i++){
			vis[i]=false;
		}
		ans=deep[1];
		getans(1,0);
		std::cout<'\n';
	}
	return 0;
}

 os：签到都这样了么。。。

Loop

给出一个数组a，每次可以把一个数字移到数组后面，经过k次操作，求可以得到的最小字典序的数组a是什么。 

思路：我们可以贪心的去利用这k次操作，用优先队列从头开始每次维护小于队首的数，最多可以维护k次，在优先队列里存这些要维护的数字，剩下的存到一个数组中，最后归并一下就可以了。

AC Code：

#include 
 
typedef long long ll;
typedef std::pair<int,int>PII;
const int N=3e5+5;
int t,n,k,num,top;
int a[N],s[N],b[N];
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>k;
        top=0,num=0;
        for(int i=1;i<=n;i++){
            std::cin>>a[i];
        }
        std::priority_queue<int>q;
        for(int i=1;i<=n;i++){
        	while(top&&s[top]
        		q.push(s[top]);
        		top--;
        		k--;
        	}
        	s[++top]=a[i];
        }
        for(int i=1,l=1;i<=n;i++){
        	if(l>top){
        		b[++num]=q.top();
        		q.pop();
        	}
        	else if(q.empty()){
        		b[++num]=s[l];
        		l++;
        	}
        	else{
        		if(q.top()>s[l]){
        			b[++num]=q.top();
        			q.pop();
        		}
        		else{
        			b[++num]=s[l];
        			l++;
        		}
        	}
        }
        for(int i=1;i<=n;i++){
        	std::cout<" \n"[i==n];
        }
    }
    return 0;
}

os：不太懂出这个题是想干什么，觉得很怪

Planar Graph

给出一个图，要求在边上修通路，即打断这条边，使得剩下的成为一棵最小生成树，但是要求输出字典序最小的边，那就需要生成字典序最大的最小生成树。

思路：就是最小生成树，Kruskal即可，注意留下的是权值大的，所以倒着取数。

AC Code：

#include 
 
typedef long long ll;
typedef std::pair<int,int>PII;
const int N=3e5+5;
int t,n,m;
std::vectorvec;
int fa[N];
 
void init(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
}
 
int getfa(int x){
	return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>m;
        vec.clear();
        init();
        for(int i=1;i<=m;i++){
        	int u,v;
        	std::cin>>u>>v;
        	vec.push_back({u,v});
        }
        std::vector<int>ans;
        for(int i=m-1;i>=0;i--){
        	int xx=getfa(vec[i].first),yy=getfa(vec[i].second);
        	if(xx==yy) ans.push_back(i+1);
        	else fa[xx]=yy;
        }
        int len=ans.size();
        std::cout<'\n';
        for(int i=len-1;i>=0;i--){
        	std::cout<' ';
        }
        std::cout<<'\n';
    }
    return 0;
}

 os：图论就很强，对于这种处理模型的能力要求很高，，看这个题代码思路并不难，但是要把这个题意转变成最小生成树。这个卡行末空格啥东西啊，有什么大病一样QAQ

Map

 现有一张大地图和一张等比例缩小的小地图，将这张小地图随意放到大地图中，必然存在一个点与大地图上同一位置的点重合，求这个点。

思路：可以这样考虑：图中满足这个条件的点分别向大小地图的四个顶点连边，他们的比例是等于边长的比例的，根据这个性质推计算公式。

AC Code：

代码还没想好怎么写，，这两天想明白了补上。。。

Shinobu loves trip

给定一个常数a和p，有个人会进行n次旅行，每次旅行的起点是s[i]，第一天的位置在s[i]，接下来每一天的位置都会变成s[i]*^(天数)%P。有q个询问，每次询问一个位置x，请问该人有多少次旅游经过了x。 

思路：学习大佬的思路

先观察数据范围，d<=20000,n<=1000,q<=1000。很容易想到对于一个x，我们枚举每一次旅游，从小到大寻找20000次，直到找到符合条件的答案或者进入死循环退出，但是时间复杂度显然不允许。因此我们可以预处理出所有的a^k直接查询，这样是没问题的。

s[i] * a^k % P = x。这个式子我们能够处理出a^k，因此我们考虑分离变量，a^k=x/s[i]modP。我们知道s[i]和x，因此我们可以直接计算出a^k，然后在我们预处理出的map中查，用限制天数d判断是否符合条件即可。时间复杂度O(nq)=1e6，理论上能过。

AC Code：

#include 
#include 
 
#define int long long
const int N=1e3+5;
int t,P,n,a,q,ans;
int s[N],d[N],fact[N];
 
int pmod(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%P;
        b>>=1;
        a=a*a%P;
    }
    return res;
}
 
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::unordered_map<int,int>mp;
    std::cin>>t;
    while(t--){
        std::cin>>P>>a>>n>>q;
        mp.clear();
        int cur=1,pos=0;
        while(pos<2e5+5&&!mp.count(cur)){
            mp[cur]=pos;
            cur=cur*a%P;
            pos++;
        }
        for(int i=1;i<=n;i++){
            std::cin>>s[i]>>d[i];
            if(s[i]) fact[i]=pmod(s[i],P-2);
        }
        while(q--){
            int x;
            std::cin>>x;
            ans=0;
            if(x==0){
                for(int i=1;i<=n;i++){
                    if(!s[i]) ans++;
                }
            }
            else{
                for(int i=1;i<=n;i++){
                    if(s[i]!=0){
                        int r=x*fact[i]%P;
                        if(mp.count(r)&&mp[r]<=d[i])
                            ans++;
                    }
                }
            }
            std::cout<'\n';
        }
    }
    return 0;
}

os：注意这样写的时限卡的很紧，必须用unordered_map才能过，而且头文件也不能用万能头，要分开写，就离谱，感觉复杂度是完全可以过的，难道因为常数大吗？？？

先这样吧QWQ