2021-2022年度第三届全国大学生算法设计与编程挑战赛(冬季赛正式赛) 【部分题题解】

现在才补，唉打的很烂。
前期还好1个小时过了5题感觉要金了，结果后面就再也没过了。
7题金，6题银，5题铜。又是一个铜首。
还是菜，感觉有机会拿金的。但是有些题确实我的掌握还是不熟。
求期望的那道题居然是原题一车的人过。
http://vj.saikr.com/contest/20/problems

• Error【二分】
• 树的果实【dfs序+莫队】
• 吃利息【签到】
• MP4【dfs】
• 展览【线性基】
• 礼物【签到】
• 看错题【线段树】

#include
using namespace std;
const int N=1e3+10;
typedef long long int LL;
LL a[N],b[N],c[N],n;
bool check(int mid)
{
    vectorA; 
    A.push_back(a[0]-mid);
    for(int i=1;i
         int l=max(a[i]-mid,1ll),r=a[i]+mid;
         if(rmax(l,A[i-1]+1)});
    }
    for(int i=0;i
        int l=a[i]-mid,r=a[i]+mid;
        if(A[i]r) return false;
    }
    return true;
}
int main(void)
{
    cin>>n;
    for(int i=0;i>a[i];
    int l=0,r=1e9;
    while(l
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout< 
树的果实【dfs序+莫队】 

 用dfs序将其转化成区间问题，然后莫队即可。
 需要注意的是，这里并不是点的权值，而是边的权值。
 我们将边的权值转化到点。例如: a->b 有c 故w[b]=c. 这样来转换。
 在求的时候我们将多余计算的左端点删除后再存答案，然后在恢复原样即可。
 
#include 
using namespace std;
typedef long long int LL;
const int N=1e5*2+10;
const int M=1e5*2+10;
int h[N],e[M],ne[M],idx;
int in[N],out[N],timestep;
int n,m,c;

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
	in[u]=++timestep;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		dfs(j,u);
	}
	out[u]=timestep;
}

LL res,pos[N],ans[N],cnt[N],a[N],w[N];//保存当前状态的值 
struct node{int l,r,id;}Node[N];
bool cmp(node a,node b)//排序 
{
	if(pos[a.l]==pos[b.l]) return a.r
	res-=(cnt[a[x]]*a[x])*(cnt[a[x]]*a[x]);
	cnt[a[x]]++;
	res+=(cnt[a[x]]*a[x])*(cnt[a[x]]*a[x]);
}
void sub(int x)
{
	res-=(cnt[a[x]]*a[x])*(cnt[a[x]]*a[x]);
	cnt[a[x]]--;
	res+=(cnt[a[x]]*a[x])*(cnt[a[x]]*a[x]);
}
int main(void)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    //如果编译开启了 C++11 或更高版本，建议使用 std::cin.tie(nullptr);
	memset(h,-1,sizeof h);
	cin>>n>>m>>c;
	for(int i=1;i<=n-1;i++)
	{
		LL u,v,c; cin>>u>>v>>c;
		add(u,v),add(v,u);
		w[v]=c;
	}
	dfs(1,-1);
  	int len=sqrt(n);//分块 
	for(int i=1;i<=n;i++) pos[i]=i/len;//分块 
	for(int i=1;i<=n;i++) a[in[i]]=w[i];
	sort(Node+1,Node+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int u; cin>>u;
		Node[i]={in[u],out[u],i};
	}
	sort(Node+1,Node+m+1,cmp);
	int l=1,r=0;//这是一个闭的区间  
	//如果l=0,r=0 则此时是一个[0,0]区间，这样的话起始就有了一个区间 
	for(int i=1;i<=m;i++)
	{
		while(Node[i].lr) add(++r);
		while(Node[i].l>l) sub(l++);
		while(Node[i].r 
吃利息【签到】 
 
#include
using namespace std;
typedef long long int LL;
LL n,m,sum;
int main(void)
{
    cin>>m>>n;
    sum=m;
    for(int i=0;i
        LL temp=sum/10;
        sum=sum+min(5ll,temp);
        sum+=5;
    }
    cout< 
MP4【dfs】 

 灵感来自
 
#include
using namespace std;
int n,sum;
void dfs(int l, int r, int k)
{
    if (r > n) r = n;//过界了
    for (int i = l; i <= r; i++)
    {
        if (i != l && i % 10 == 0) return;//该位枚举完了
        sum++;
        if (sum <= k)
        {
            printf("%lld.mp4n", i);
            if (sum == k)
                return;
        }
        if (i * 10 <= n) dfs(i * 10, i * 100 - 1, k);
    }
    return;
}
int main()
{
    cin>>n;
    dfs(1, 9, 50);
    return 0;
}
 
展览【线性基】 

 线性基板子题。
 
#include
#include
using namespace std;
const int N = 1e5 + 10;
long long n, p[N], a[N], cnt;
void add(long long v)
{
    for(int i = 1; i <= cnt; i++)
        v = min(v, v ^ p[i]);

    if(v)
    {
        p[++cnt] = v;
        sort(p + 1, p + cnt + 1, greater());
    }
}
long long query_max()
{
    long long v = 0;
    for(int i = 1; i <= cnt; i++) v = max(v, v ^ p[i]);
    return v;
}
int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%lld", a + i), add(a[i]);
    cout< 
礼物【签到】 
 
#include
using namespace std;
typedef long long int LL;
const int N=1e5*5+10;
LL n,m,t,sum;
int a[N];
int main(void)
{
    cin>>n;
    for(int i=0;i>a[i];
    sort(a,a+n);
    cout< 
看错题【线段树】 

 找规律的题。题目给的是满二叉树。
 
#include
using namespace std;
typedef long long int LL;
const int N=1e5*4+10;
LL sum=0;
int main()
{
	//cout<<(8*36)+(4*10)+(4*26)+ (2*3)  +(2*7) + (2*11)+ (2*15)+(1+2+3+4+5+6+7+8)<<'n';//原来     540
    //cout<<(8*48)+(4*22)+(4*26)+ (2*11) +(2*11)+ (2*11)+ (2*15)+(5+6+7+4+5+6+7+8)<<'n';//加3个点每个点加4 720
	//cout<<(8*40)+(4*14)+(4*26)+ (2*7)  +(2*7) + (2*11)+ (2*15)+(5+2+3+4+5+6+7+8)<<'n';//加1个点每个点加4 600
    //说明一个点加60  60/4==15==(1<>n>>m;
	LL deep=0;
	for(int i=1;i<=n;i++) 
	{
		int x; cin>>x;
		sum+=x;
	}
	while(n) n/=2,deep++;
	sum=sum*((1<
		LL l,r,x; cin>>l>>r>>x;
		sum+=(r-l+1)*((1ll<