第25次CCF-CSP认证题解

第一题未初始化警告

#include<bits/stdc++.h>
using namespace std;
int n,k,a,b,ans;
int vis[100010];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    vis[0]=1;
    while(k--){
        cin>>b>>a;
        if(!vis[a])ans++;
        vis[b]=1;
    }
    cout<<ans;
}

第二题

一开始读错题目了，以为是q>=a&&q<a+b

每一个活动的贡献是a-b+1,a这个区间，弄一下差分就好了

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,k,a[N],b[N],ans,c[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        c[max(a[i]-b[i]+1,1)]+=1;
        c[a[i]+1]-=1;
    }
    for(int i=1;i<N;i++)c[i]+=c[i-1];
    while(m--){
        int q;
        cin>>q;
        q+=k;
        cout<<c[q]<<'\n';
        
    }
}

第三题

#include <bits/stdc++.h>
using namespace std;
const int mod = 929, N = 1e5 + 5;
int w, s, k, pre = 1;
string str;
int t[N], tmp[N], g[N], d[N];
int main()
{
	cin >> w >> s >> str;
	if (s == -1) k = 0;
	else k = pow(2, s + 1);
	int idx = 0;
	for (char i : str)
	{
		if (i >= 'A' && i <= 'Z')
		{
			if (pre != 1) t[idx++] = 28; 
			if(pre == 2) t[idx++] = 28;
			t[idx++] = i - 'A';
			pre = 1;
		}
		else if (i >= 'a' && i <= 'z')
		{
			if (pre != 2) t[idx++] = 27;
			t[idx++] = i - 'a';
			pre = 2;
		}
		else
		{
			if (pre != 3) t[idx++] = 28;
			t[idx++] = i - '0';
			pre = 3;
		}
	}
	if (idx & 1) t[idx++] = 29;
	int len = 0;
	for (; len < idx; len += 2) tmp[len / 2] = t[len] * 30 + t[len + 1];
	len /= 2;
	int sum = len + 1 + k;
	if (sum % w)
		for (int i = 0; i < w - (sum % w); ++i) tmp[len++] = 900;

	int c = -3;
	g[0] = 1;
	for (int i = 1; i <= k; ++i, c = c * 3 % mod)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			g[j + 1] = (g[j] * c + g[j + 1]) % mod;
		}
	}
	d[0] = len + 1;
	for (int i = 1; i <= len; ++i) d[i] = tmp[i - 1];
	
	for (int i = 0; i <= len; i++)
	{
		int x = d[i];
		d[i] = 0;
		for (int j = 1; j <= k; j++)
		{
			d[i + j] = (d[i + j] - x * g[j]) % mod;
		}
	}

	cout << len + 1 << '\n';
	for (int i = 0; i < len; ++i) cout << tmp[i] << '\n';
	for (int i = len + 1; i <= len + k; ++i) cout << (-d[i] % mod + mod) % mod << '\n';
	return 0;
}

第四题

这是一道感觉能拿70分的代码，但是不知道错在哪里，听说要用两个堆来维护一下一个可删除堆才是这道题的正解

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=2e5+10;
struct node{
    int a,b,c;
};
unordered_map<int,int>mp[N],t[N];
unordered_set<int>S;
vector<node>day[N];
int vis[N];
int e,cnt;
inline int find(int x){
    int ans=0;
    int ans_id=0;
    for(auto &s:mp[x]){
        int k=s.first;
        int v=s.second;
        if(v>ans)ans=v,ans_id=k;
        else if(v==ans)ans_id=min(ans_id,k);
    }
    return ans_id;
}
void update(int d){
    for(auto t:day[d]){
        int a=t.a;
        int b=t.b;
        int c=t.c;
        mp[a][b]-=c,mp[b][a]-=c;
        if(mp[a][b]==0){
            e--;
            //auto iter=mp[a].find(b);
            mp[a].erase(mp[a].find(b));
            //iter=mp[b].find(a);
            mp[b].erase(mp[b].find(a));
        }
        if(find(a)==0)S.insert(a);
        if(find(b)==0)S.insert(b);
        int prea=vis[a];
        vis[a]=find(a);
        int preb=vis[b];
        vis[b]=find(b);
        //如果他们两个曾经互为对象，
        if(prea==b&&preb==a){
            //但现在不是了cnt--
            if(vis[a]!=b||vis[b]!=a){
                cnt--;
                //如果a跟现在的vis[a]互为对象cnt++
                int c=vis[a];
                if(vis[c]==a)cnt++;
                //如果b跟现在的vis[b]互为对象cnt++
                int d=vis[b];
                if(vis[d]==b)cnt++;
            }
            
        }
        else{
            //删边不影响
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)S.insert(i);
    for(int i=1;i<=m;i++){
        update(i);
        int k;
        cin>>k;
        while(k--){
            int a,b,c,d;
            cin>>a>>b>>c>>d;
            //if(!mp[a].count(b))e++;
            mp[a][b]+=c;
            mp[b][a]+=c;
            if(S.count(a))S.erase(a);
            if(S.count(b))S.erase(b);
            day[i+d].push_back({a,b,c});
            int prea=vis[a];
            vis[a]=find(a);
            int preb=vis[b];
            vis[b]=find(b);
            //如果他们两个曾经不互为对象，
            if(prea!=b||preb!=a){
                //但现在是了cnt++
                if(vis[a]==b&&vis[b]==a){
                    cnt++;
                    //如果a跟曾经的vis[a]互为对象cnt--
                    int c=prea;
                    if(vis[c]==a)cnt--;
                    //如果b跟曾经的vis[b]互为对象cnt--
                    int d=preb;
                    if(vis[d]==b)cnt--;
                }
                
                
            }
            else{
                //a跟b之前就是对象，现在权重还加大了所以不用管
            }
        }
        int l;
        cin>>l;
        while(l--){
            int x;
            cin>>x;
            int y=find(x);
            cout<<y<<'\n';
        }
        for(int i=1;i<=n;i++){
            cout<<"find "<<i<<" = "<<find(i)<<endl;
        }
        cout<<"通信孤岛="<<S.size()<<endl;
        cout<<"通信对="<<cnt<<endl;
        int p,q;
        cin>>p>>q;
        if(p)cout<<S.size()<<'\n';
        if(q)cout<<cnt<<'\n';
    }
}

第23次CCF-CSP

第五题

因为有A的存在，这道题被要求强制在线，

而且有查询树上区间的操作，这里有两种操作，一个是树链剖分，一个是lct

而树链剖分是对静态序列建树，这道题要求动态加边所以用lct来写

同时，因为会查询之前的节点信息，所以我们不能真的删掉节点
那么如何找到真正的节点编号呢
我们发现每一个增加的节点一定会被放在某一层里，而这某一层就是排名
而且查询和更新的链路径信息一定是第i名到第j名
至此，找什么链找哪条链就知道了
如何找到第s天第x名选手的节点编号呢
我们可以插入的时候把{第i天，节点编号}push_back进一个容器rank里面
找的时候就是去rank[x]里面找到符合条件的第一个，也就是第一个小于等于{s，0}的节点，也就是前驱
你二分也可以，lower_bound也可以
lct裸题

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rank _rank
const int N=1e6+10;
int m,p,T,A,cur,idx,op,s,l,r,x,dep[N],fa[N],y;
typedef pair<int,int>PII;
vector<PII>rank[N];
struct node{
    int s[2],p,v;
    int sum,rev,mul;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
    #define lx tr[x].s[0]
    #define rx tr[x].s[1]
}tr[N];
bool isroot(int u){
    return tr[tr[u].p].s[0]!=u && tr[tr[u].p].s[1]!=u;
}
void pushup(int u){
    tr[u].sum=tr[u].v;
    if(ls)tr[u].sum+=tr[ls].sum;
    if(rs)tr[u].sum+=tr[rs].sum;
    tr[u].sum%=p;
    
}
void pushrev(int u){
    swap(ls,rs);
    tr[u].rev^=1;
}
void pushdown(int u){
    if(tr[u].rev){
        pushrev(ls);
        pushrev(rs);
        tr[u].rev=0;
    }
    if(tr[u].mul!=1){
        tr[ls].mul=tr[ls].mul*tr[u].mul %p;
        tr[ls].sum=tr[ls].sum*tr[u].mul %p;
        tr[ls].v=tr[ls].v*tr[u].mul %p;
        
        tr[rs].mul=tr[rs].mul*tr[u].mul %p;
        tr[rs].sum=tr[rs].sum*tr[u].mul %p;
        tr[rs].v=tr[rs].v*tr[u].mul %p;
        
        tr[u].mul=1;
    }
}
void rotate(int x){
    int y=tr[x].p,z=tr[y].p;
    int k=tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y,tr[y].p=x;
    pushup(y),pushup(x);
}
void splay(int x){
    static int stk[N];
    int tt=0,t=x;
    stk[++tt]=t;
    while(!isroot(t))stk[++tt]=t=tr[t].p;
    while(tt)pushdown(stk[tt--]);
    while(!isroot(x)){
        int y=tr[x].p,z=tr[y].p;
        if(!isroot(y)){
            if((tr[z].s[1]==y)^(tr[y].s[1]==x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){ // 建立一条从根到x的路径，同时将x变成splay的根节点
    int z=x;
    for(int y=0;x;y=x,x=tr[x].p){
        splay(x);
        tr[x].s[1]=y,pushup(x);
    }
    splay(z);
}
void makeroot(int x){
    access(x);
    pushrev(x);
}
int findroot(int x){// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
    access(x);
    while(lx)pushdown(x),x=lx;
    splay(x);
    return x;
}
void split(int x,int y){
    makeroot(x);
    access(y);
}
void link(int x,int y){
    makeroot(x);
    if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)==x&&rx==y&&!tr[y].s[0]){
        tr[y].p=rx=0;
        pushup(x);
    }
}
int find(int s,int x){
    //去排名为x的节点里面找第一个小于等于s的节点编号
    int l=0,r=rank[x].size()-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(rank[x][mid].first<=s)l=mid;
        else r=mid-1;
    }
    return rank[x][l].second;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>m>>p>>T;
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x;
            if(T)x^=A;
            if(x>0){
                ++idx;
                tr[idx].v=tr[idx].sum=x;
                tr[idx].mul=1;
                if(cur)link(cur,idx);
                fa[idx]=cur,dep[idx]=dep[cur]+1;
                rank[dep[idx]].push_back({i,idx});
                cur=idx;
            }
            else cur=fa[cur];
        }
        else if(op==2){
            cin>>s>>l>>r>>y;
            if(T)y^=A;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            tr[r].v=tr[r].v*y%p;
            tr[r].sum=tr[r].sum*y%p;
            tr[r].mul=tr[r].mul*y%p;
        }
        else{
            cin>>s>>l>>r;
            l=find(s,l);
            r=find(s,r);
            split(l,r);
            cout<<tr[r].sum<<'\n';
            if(T)A=tr[r].sum;
        }
    }
}

4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=16,M=1<<N;
int n,k;
double p[N],f[M][N*5+1];
double dfs(int x,int sum,int need){
    if(f[x][sum]>=0)return f[x][sum];
    if(sum>=need*k)return f[x][sum]=0;
    f[x][sum]=0;
    for(int i=0;i<n;i++){
        if(x>>i&1)f[x][sum]+=p[i]*(dfs(x,sum+1,need)+1);
        else f[x][sum]+=p[i]*(dfs(x^(1<<i),sum,need-1)+1);
    }
    return f[x][sum];
}
signed main(){
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>p[i];
    memset(f,-1,sizeof f);
    // cout<<fixed<<dfs(0,0,n);
    printf("%.10lf",dfs(0,0,n));
}

3

我去年打的时候只拿了70分，应该是爆内存了，这是别人的用循环队列来优化的100分写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;
const double INF = 1e8;

int n, s, p, T;
double dt;
int h[N], e[N], D[N], ne[N], idx;
double W[N], v[N], u[N], a[N], b[N], c[N], d[N];
int r[N], cnt[N];
double I[1024][N / 2];

static unsigned long _next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    _next = _next * 1103515245 + 12345;
    return((unsigned)(_next/65536) % 32768);
}

void add(int a, int b, double c, int d)
{
    e[idx] = b, W[idx] = c, D[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &s, &p, &T);
    scanf("%lf", &dt);
    for (int i = 0; i < n;)
    {
        int rn;
        scanf("%d", &rn);
        double vv, uu, aa, bb, cc, dd;
        scanf("%lf%lf%lf%lf%lf%lf", &vv, &uu, &aa, &bb, &cc, &dd);
        for (int j = 0; j < rn; j ++, i ++ )
        {
            v[i] = vv, u[i] = uu, a[i] = aa, b[i] = bb, c[i] = cc, d[i] = dd;
        }
    }

    for (int i = n; i < n + p; i ++ ) scanf("%d", &r[i]);

    int mod = 0;
    while (s -- )
    {
        int a, b, d;
        double c;
        scanf("%d%d%lf%d", &a, &b, &c, &d);
        add(a, b, c, d);
        mod = max(mod, d + 1);
    }

    for (int i = 0; i < T; i ++ )
    {
        int t = i % mod;
        for (int j = n; j < n + p; j ++ )
            if (r[j] > myrand())
            {
                for (int k = h[j]; ~k; k = ne[k])
                {
                    int x = e[k];
                    I[(t + D[k]) % mod][x] += W[k];
                }
            }

        for (int j = 0; j < n; j ++ )
        {
            double vv = v[j], uu = u[j];
            v[j] = vv + dt * (0.04 * vv * vv + 5 * vv + 140 - uu) + I[t][j];
            u[j] = uu + dt * a[j] * (b[j] * vv - uu);

            if (v[j] >= 30)
            {
                for (int k = h[j]; ~k; k = ne[k])
                {
                    int x = e[k];
                    I[(t + D[k]) % mod][x] += W[k];
                }
                cnt[j] ++ ;
                v[j] = c[j], u[j] += d[j];
            }
        }

        memset(I[t], 0, sizeof I[t]);
    }

    double minv = INF, maxv = -INF;
    int minc = INF, maxc = -INF;

    for (int i = 0; i < n; i ++ )
    {
        minv = min(minv, v[i]);
        maxv = max(maxv, v[i]);
        minc = min(minc, cnt[i]);
        maxc = max(maxc, cnt[i]);
    }

    printf("%.3lf %.3lf\n", minv, maxv);
    printf("%d %d\n", minc, maxc);

    return 0;
}

2

每一个p都会确定最后的数组长啥样，以及答案是什么
观察发现p确定的是一个答案的差分数组
枚举每一段相岭数字之间的关系求差分数组的前缀最大值

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,x,pre,sum,ans,a[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x>pre)a[pre]++,a[x]--;
        pre=x;
    }
    for(int i=0;i<=1e4;i++){
        sum+=a[i];
        ans=max(ans,sum);
    }
    cout<<ans;
}

1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
#define int long long
int n,maxx,minn,pre,x;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cin>>pre;
    maxx=minn=pre;
    for(int i=2;i<=n;i++){
        cin>>x;
        if(x>pre)minn+=x;
        maxx+=x;
        pre=x;
    }
    cout<<maxx<<'\n'<<minn;
}

24

1

#include<bits/stdc++.h>
using namespace std;
int n,k,x,ans;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    int pre;
    cin>>pre;
    for(int i=1;i<n;i++){
        cin>>x;
        
        ans+=(x-pre)*i;
        
        pre=x;
    }
    ans+=(k-pre)*n;
    cout<<ans;
}

2

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int a[N];
int R;

LL get(int l, int r)  // 求g[l] + g[l + 1] + ... + g[r]
{
    if (l / R == r / R) return (LL)(r - l + 1) * (l / R);
    int a = l / R + 1, b = r / R - 1;
    LL res = (a + b) * (LL)(b - a + 1) / 2 * R;  // 中间部分
    res += (a - 1) * (LL)(a * R - l);  // 左边界
    res += (b + 1) * (LL)(r - (b * R + R) + 1);  // 右边界
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    a[n + 1] = m;
    R = m / (n + 1);

    LL res = 0;
    for (int i = 0; i <= n; i ++ )
    {
        int l = a[i], r = a[i + 1] - 1;
        int x = l / R, y = r / R;
        if (y <= i || x >= i)
        {
            res += abs((LL)i * (r - l + 1) - get(l, r));
        }
        else
        {
            int mid = i * R;
            res += abs((LL)i * (mid - l + 1) - get(l, mid));  // 左半边
            res += abs((LL)i * (r - mid) - get(mid + 1, r));  // 右半边
        }
    }

    printf("%lld\n", res);
    return 0;
}

3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
struct NODE
{
	int id, sum, blockid;
	set<int> task;
	bool operator < (const NODE& a)const
	{
		if (sum > a.sum) return true;
		else if (sum == a.sum)
			if (id > a.id) return true;
		return false;
	}
}node[N];
int n, m, k, f, a, na, pa, paa, paar;
priority_queue<NODE> q;
set<int> block[N];
void f1()
{
	vector<NODE> vec, vec2, vec3;
	if (na)
	{
		for (int i = 1; i <= n; ++i)
			if (node[i].blockid == na)
				vec.push_back(node[i]);
	}
	else for (int i = 1; i <= n; ++i) vec.push_back(node[i]);
	if (pa)
	{
		for (auto i : vec)
		{
			if (block[i.blockid].find(pa) != block[i.blockid].end())
				vec2.push_back(i);
		}
	}
	else vec2 = vec;
	if (paa)
	{
		for (auto i : vec2)
		{
			if (i.task.find(paa) != i.task.end()) continue;
			vec3.push_back(i);
		}
	}
	else vec3 = vec2;
	for (auto i : vec3) q.push(i);
	return;
}
void f2()
{
	while (f && q.size())
	{
		NODE t = q.top();
		q.pop();
		cout << t.id << ' ';
		node[t.id].sum++;
		node[t.id].task.insert(a);
		block[t.blockid].insert(a);
		if (a != paa) { t.sum++; q.push(t); }
		--f;
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		node[i].id = i;
		cin >> node[i].blockid;
	}
	cin >> k;
	while (k--)
	{
		cin >> f >> a >> na >> pa >> paa >> paar;
		f1();
		f2();
		if (f && !paar)
		{
			paa = 0;
			f1();
			f2();
		}
		while (f--) cout << "0 ";
		cout << '\n';
		while (q.size()) q.pop();
	}
	return 0;
}