2022—SWJTU-寒假ACM校队选拔赛第二场-题解

2024-02-24 14:14:34

A - *楼梯

算法分析

队列模拟即可

要转变方向当且仅当不同方向的人已抵达电梯,且该方向的下一个人还未到达电梯

AC code

#include<iostream>
#include<queue>
using namespace std;
queue<int> q0,q1;
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b == 0) q0.push(a);
        else q1.push(a);
    }
    int ans = 0;
    while(q0.size() && q1.size())
    {   
        auto up = q0.front(),down = q1.front();
        //printf("up = %d,down = %d\n",up,down);
        if(up < down)
        {
            ans += 10;
            while(q0.front() < ans && q0.size())
            {
                ans = max(ans,q0.front() + 10);
                //printf("q0.ans = %d\n",ans);
                q0.pop();
            }
        }
        else 
        {
           ans += 10;
           while(ans > q1.front() && q1.size())
           {
               ans = max(ans,q1.front() + 10);
               //printf("q1.ans = %d\n",ans);
               q1.pop();
           }
        }
    }
    ans += 10;
    int res = 0;
    while(q0.size())
    {
        res = q0.front() + 10;
        q0.pop();
    }
    while(q1.size())
    {
        res = q1.front() + 10;
        q1.pop();
    }
    printf("%d\n",max(res,ans));
    return 0;
}

B - cold爱吃小蛋糕

算法分析

不会吃重量小于的蛋糕且每次吃掉的部分不会超过蛋糕重量的一半,那么最后就会浪费上取整重量的蛋糕。

AC code

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
 
signed main()
{
    int sum = 0;
    int n,k;
    scanf("%lld%lld",&n,&k);
    for(int i = 1;i <= n;i ++)
    {
        int x;scanf("%lld",&x);
        sum += x;
    }
    
    if(sum < k) puts("0");
    else 
    {
        if(k % 2 == 0) printf("%lld\n",sum - (k / 2));
        else printf("%lld\n",sum - (k / 2) - 1);
    }
    return 0;
}

C - 郑老板玩方块

算法分析

暴力判断正方体顶点间的距离,设边长为一个单位长度的话,一个顶点和剩余 7 个顶点间存在一条,三条 ,三条那么就把所有的枚举出来,排序,判断一下是否满足此条件即可

AC code

#include<bits/stdc++.h>
const int N =  10;
using namespace std;
int dis[1000];
typedef struct Point
{
    int x,y,z;
}PT;
PT pos[N];
 
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int cnt = 0;
        for(int i = 1;i <= 8;i ++)
        scanf("%d%d%d",&pos[i].x,&pos[i].y,&pos[i].z);
        for(int i = 1;i <= 8;i ++)
        {
            for(int j = 1;j <= 8;j ++)
            {
                if(i == j) continue;
                dis[cnt] = (pos[i].x - pos[j].x) * (pos[i].x - pos[j].x) + (pos[i].y - pos[j].y) * (pos[i].y - pos[j].y) + (pos[i].z - pos[j].z) * (pos[i].z - pos[j].z);
                cnt ++;
            }
        }
        sort(dis,dis + cnt);
        if(dis[0] == 0) {puts("NO"); continue;}
        if(dis[0] != dis[23] || dis[24] != dis[47] || dis[48] != dis[55]) 
        {
            puts("NO");
            continue;
        } 
        else if(dis[0] * 2 != dis[24] || dis[0] * 3 != dis[55])
        {
            puts("NO");
            continue;
        }
        else
        {
            puts("YES");
        }
    }
    return 0;
}

D - 风神瞳

算法分析

最短路 + 完全背包

为了使利益最大化,我们肯定使希望到达各个点的时间最短,那么就只需要跑一遍 dijkstra 求出最短路,那么问题就变成了时间 T 内能获得的最大价值,跑一遍完全背包就搞定了。

AC code

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 3e3 + 10;
const int M = N * 2;

int dist[N],h[N],e[M],ne[M],w[M],idx;
bool st[M];
int a[N],f[9000000 + 10];
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}


void dijkstra()  // 求1号点到n号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(w, 1,sizeof w);
    int n,m,t;
    cin >> n >> m >> t;
    for(int i = 2;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= m;i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a, b, 1);
        add(b, a, 1);
    }
    dijkstra();
    
    for(int i=2;i<=n;i++)
        w[i]=dist[i]*2;
    for(int i=2;i<=n;i++)
        for(int j=w[i];j<=t;j++)
            f[j]=max(f[j],f[j-w[i]]+a[i]);
    for(int i=1;i<=t;i++)
        printf("%d ",f[i]);

    return 0;
}

E - cold不会字符串

算法分析

没什么人做的原因应该是题目读假了。

题目的意思是已知这么一段错误的代码然后给我们一个匹配串，问能否构造一个串使得这个算法得到的答案是错误的。

很明显这段代码错误的原因在于指针没有回溯。那么怎样的串我们可以把它 hack 掉呢

倘若的一定会被 hack ,学过KMP的同学知道,KMP就是求解前后缀匹配情况即数组回溯进行匹配的,但改错误代码其没有回溯,因此产生了错误。那么知道了这点以后,甚至可以不用求数组了,直接判断串中是否有与相同的,有相同的必然是了

AC code

#include<bits/stdc++.h>
using namespace std;
char s[100000 + 10];
int main() 
{
	int n ;
	cin >> n;
	cin >> s + 1;
	int flag = 1;
	for(int i = 2; i <= n;i ++)
	{
		if(s[i] == s[1]) flag = 0;
	}
	if(flag) cout<<"Correct"<<"\n";
	else cout<<"Wrong Answer"<<"\n";
	return 0;
}

F - 你一定会种树吧2.0

算法分析

线段树(不要再对着线段树写暴力啦

AC code

#include <bits/stdc++.h>

#define il inline
#define fi first
#define se second
#define int long long
#define pii pair<int, int>
#define pll pair<long, long>
#define pb(x) push_back(x)
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define mem(num) memset(num,0,sizeof num)
#define lowbit(x) ((x)&-(x))

using namespace std;

const int mod = 998244353;
const int maxn = 1e6 + 100;

int n, m;
int a[maxn];
struct node{
	int l, r;
	int mx;
	int flag;
} sgt[maxn<<2];

int judge(int x){
	return bitset<32>(x).count() == 0;
}

void push_up(int x){
	sgt[x].mx = max(sgt[x<<1].mx, sgt[x<<1|1].mx);
	sgt[x].flag = sgt[x<<1].flag | sgt[x<<1|1].flag;
}

void build(int x, int l, int r){
	if(l == r) {
		sgt[x] = {l, r, a[l], a[l]};
		return;
	}
	sgt[x] = {l,r};
	int mid = l + r >> 1;
	build(x<<1, l, mid); build(x<<1|1, mid + 1, r);
	push_up(x);
}

void update(int x, int p, int v){
	if(sgt[x].l == p && sgt[x].r == p) {
		sgt[x].mx = v;
		sgt[x].flag = v;
		return;
	}
	int mid = sgt[x].l + sgt[x].r >> 1;
	if(p<=mid) update(x<<1,p,v); 
	else update(x<<1|1,p,v);
	push_up(x);
}

void modify(int x, int l, int r, int v){
	if(!((~v)&sgt[x].flag)) return;
	if(sgt[x].l == sgt[x].r) {
		sgt[x].mx &= v;
		sgt[x].flag &= v;
		return;
	}
	int mid = sgt[x].l + sgt[x].r >> 1;
	if(l<=mid) modify(x<<1,l,r,v);
	if(r>mid) modify(x<<1|1,l,r,v);
	push_up(x);
}


inline int query(int x, int l ,int r){
	if(sgt[x].l>=l&&sgt[x].r<=r) return sgt[x].mx;
	int mid = sgt[x].l + sgt[x].r >> 1;
	if (r <= mid)return query(x << 1, l, r);
    else if (l > mid)return query(x << 1 | 1, l, r);
    else{
    	int res = 0;
		res = max(res,query(x<<1,l,r));
		res = max(res,query(x<<1|1,l,r));
		return res;
    }
}

inline void solve(){
	cin >> n;
	cin >> m;
	for (int i = 1; i <= n; ++ i) {
		cin>>a[i];
	}
	build(1,1,n);
	string op;
	int l, r, x, v;
	for (int i = 1; i <= m; ++ i) {
		cin>>op;
		if(op[0] == 'A') {
			//cout<<1<<endl;
			cin>>l>>r>>v;
			modify(1,l,r,v);
		} else if(op[0] == 'U'){
			cin>>x>>v;
			update(1,x,v);
		} else {
			cin>>l>>r;
			cout<<query(1,l,r)<<"\n";
		}
	}
	
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);std::cout.tie(NULL);
	int _ = 1;
	//cin >> _;
	while (_--) {
		solve();
	}
}

G - 郑老板爱玩博弈论

算法分析

老师和每个学生都要玩过，用自己的x点数换y个点数，x>y?额外多10个，反之少10个。

思路很简单，其实稍微分析一下就可以知道两人比赛获得点数均等，这是一场公平的游戏,期望是0。

AC code

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

int main()
{
    int n;
    cin >> n;
	puts("0.0000");
	return 0;
}

H - 琴

算法分析

整除分块看看这个

看完文章这题就能 A 掉了

AC code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        LL res = 0x3f3f3f3f;
        LL n,m;
        scanf("%lld%lld",&n,&m);
        if(m % n == 0) puts("0");
        else if(n > m) printf("%lld\n",n - m);
        else 
        {
            for(LL l = 1,r;l <= n;l = r + 1)
            {
                r = min(n,(m - 1) / ((m - 1) / l));
                if(r <= n) res = min(res,((m - 1) / l )* l);
            } 
            printf("%lld\n",n - m + res);
        }
       
    }
    return 0;
}

考虑离线莫队。
题目相当于找出每段区间里每个数字的所有因子，找到其出现次数最多的因子的个数。
但是 ai 最大可达到 , 因子数量太多。仔细想想会发现我们并不需要求出所有因子，只需要求出所有质因子即可，又因为一个数的质因子个数非常少（最多不超过 7 个，记为），因此我们可以预处理所有数的质因子后把问题近似为求区间众数。维护每个质因子出现的次数和出现 i 次的质因子的数量，即可离线后使用莫队求解本题。
由于 n 和 q 为同一数量级，总时间复杂度为
注意：本题时限较为严格，如果将每个数拆成个质因数然后利用分块求区间众数，或者采用不当的筛素数方法，或者使用回滚莫队等，都可能造成常数过大而，需要一些卡常技巧才能通过。

AC code

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

const int N=5e4+10, B=220, X=1e6+10;

vector<int> V[X];
int numofp[X], num[N];
int maxp;
int n, m;
int a[N];
bool visp[X];
vector<int> vis;

//prime
void getprime(int i){
	if(V[i].size()) return;
		int x=i;
		for(int j=2; j*j<=x; ++j){
			if(x%j==0){
				V[i].push_back(j);
				while(x%j==0){
					x/=j;
				}
			}
		}
		if(x>1) V[i].push_back(x);
}

//modui
struct Query{
	int l, r, ans, id;
	Query(int l=0, int r=0, int id=0):l(l),r(r),id(id){}
	bool operator<(const Query&t)const{
		int a=l/B, b=t.l/B;
		if(a!=b) return a<b;
		return r<t.r;
	}
}q[N];

void Add(int w){
//	printf("%d\n", a[w]);
	for(auto&p:V[a[w]]){
//		printf("+ %d\n", p);
		num[numofp[p]]--;
		numofp[p]++;
		num[numofp[p]]++;
		maxp=max(maxp,numofp[p]);
//		printf("maxp=%d\n", maxp);
	}	
}

void Del(int w){
	for(auto&p:V[a[w]]){
		num[numofp[p]]--;
		numofp[p]--;
		num[numofp[p]]++;
		if(num[maxp]==0) maxp--;
	}
}

int Getans(){
	return maxp;
}

bool cmp(const Query&q1, const Query&q2){
	return q1.id<q2.id;
}

int main(){
	int T; cin>>T;
	//init V[]
//	getprime();
	//solve
	while(T--){
		//input n, q, a[], query[]
		scanf("%d%d", &n, &m);
		num[0]=X;
		for(int i=1; i<=n; ++i){
			scanf("%d", a+i);
			getprime(a[i]);
		}
		for(int i=1, l, r; i<=m; ++i){
			scanf("%d%d", &l, &r);
			q[i]=Query(l,r,i);
		}
		q[0]=Query(1,1,0);
		//prime factor of a[]
		for(int i=1; i<=n; ++i){
			for(auto&j:V[a[i]]){
				if(!visp[j]){
					visp[j]=true;
					vis.push_back(j);
				}
			}
		}
		//block, sort
		sort(q,q+m+1);
		//solve
		int l=1, r=0;
		for(int i=0; i<=m; ++i){
//			printf("l=%d r=%d\n", l, r);
			while(l<q[i].l) Del(l++); 
			while(l>q[i].l) Add(--l);
			while(r<q[i].r) Add(++r);
			while(r>q[i].r) Del(r--);
			q[i].ans=Getans();
		}
		//print
		sort(q,q+m+1,cmp);
		for(int i=1; i<=m; ++i){
			printf("%d\n", q[i].ans);
		}
		//init
		maxp=0;
		for(int i=1; i<=n; ++i){
			V[i].clear();
			num[i]=0;
		}
		for(auto&i:vis){
			visp[i]=false;
			numofp[i]=0;
		}
		vis.clear();
	}
	
}

J - 简单水题

算法分析

看看这个

AC code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int N = 510, M=510;
const LL P = 998244353;
 
int n, m, p, q;
int mp[N][M];
int f[2][M][N + M];
 
int main(void)
{
    cin >> n >> m >> p >> q;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>mp[i][j];
 
    if(mp[1][1]) f[1][1][0]=1;
    else f[1][1][1]=1;
 
     
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(i==1&&j==1) continue;
            if(mp[i][j]){
                for(int k=0;k<M+N;++k)
                {
                    f[1][j][k]=(f[1][j-1][k]+f[0][j][k])%P;
                }
            }
            else{
                f[1][j][0]=0;
                for(int k=1;k<M+N;++k)
                    f[1][j][k]=(f[1][j-1][k-1]+f[0][j][k-1])%P;
            }
             
        }
        for(int j=1;j<=m;++j)
            for(int k=0;k<M+N;++k)
                f[0][j][k]=f[1][j][k];
    }
    int ans=0;
    for(int i=p;i<=n+m-1-q;++i)
        ans=(ans+f[0][m][i])%P;
    cout<<ans<<'\n';
 
    return 0;
}

K - 学不会的知识

算法分析

显然, 这个问题是单调的, 即大的 cache 表现的一定不比小 cache 更差, 二分 cache 的大小就行了.
主要是 check 函数的写法, 可以用一个优先队列和一个 map, 优先队列按照最近访问时间排序, 修改一个块的最近访问时间直接在 map 里修改, 然后每次从优先队列取出堆顶元素的时候判断优先队列里记录的时间和 map 里记录的时间是否一致, 不一致就把 map 里记录的最近访问时间加上去再 push 进优先队列, 然后看下一个元素, 这样的 check 是的, 总时间复杂度
或者把 cache 里的元素按照最近访问时间顺序组织成一个链表, 然后用 unordered_map 记录 cache 里每个块的链表节点的位置, 这样链表头就是下一个要被替换的块, 加入块在链表尾加入, 访问 cache 里已有的元素就直接把他从链表中间删掉然后在链表尾加进去. 这样总的复杂度只需要

AC code

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

typedef long long LL;
const int N = 1e5 + 10;
map<int, int> M;
int mp[N];
int n, k;
LL a[N];
vector<LL> V;

bool check(int m){
    int cnt = 0;
    for(auto&i:M){
        mp[i.second] = 0;
    }
    M.clear();
    for (int i = 1; i <= n; ++i)
    {
        int val = a[i];
        if (mp[val]){
            cnt++;
            M.erase(mp[val]);
            mp[val] = i;
            M[i] = val;
        }
        else if(M.size()<m){
            mp[val] = i;
            M[i] = val;
        }else{
            auto t = M.begin();
            int v = t->second;
            M.erase(t);
            mp[v] = 0;
            mp[val] = i;
            M[i] = val;
        }
    }
    return cnt >= k;
}

void lisan(){
    sort(V.begin(), V.end());
    for (int i = 1; i <= n; ++i){
        a[i] = lower_bound(V.begin(), V.end(), a[i]) - V.begin()+1;
    }
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        scanf("%lld", a + i);
        V.push_back(a[i]);
    }
    lisan();
    int l = 1, r = n, mid;
    while(l<r-1){
        mid = l + r >> 1;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    int ans;
    if(check(l))
        ans = l;
    else if(check(r)) ans=r;
    else ans=-1;
    if(ans>0){
    	cout << ans << endl;
	}else{
		cout<<"cbddl"<<endl;
	}
    
}

L - 写不完了

算法分析

可以简化成这样一个问题

一颗个节点的无根树, 边权非负, 每个点独立完成作业用时 (非负), 去抄另一个在时刻已经完成作业的的作业, 用时为 , 其中是两点间的距离. 带修改点权和边权, 询问每个点最早完成作业的时间 (的异或和).

先考虑查询, 暴力做法, 对每个点来说, 去找已经完成作业的点, 看看能不能抄他的作业使得时间变短.

或者这样考虑, 已完成作业的点, 去给其他点抄作业, 能不能让其他点的时间变短. 复杂度(直接求两点间距离), 或者 (用倍增或树链剖分求两点间距离).
仔细思考上述暴力, 发现暴力的过程和 Dijkstra 算法几乎一模一样. 注意到两点之间的路径唯一. 假设从到需要经过 , 不妨设需要去松弛 , 那么一定会先去松弛 , 然后再去松弛 , 这样和去松弛的效果等价. 所以只需要考虑真实存在的边即可. 用堆优化的 Dijkstra 可以做到存在次查询, 这样总复杂度会达到无法通过本题, 需要一个的做法.根据上述分析, 一个点只会被他的儿子或者父亲更新.

所以考虑换根 dp. 第一次 dfs 求为仅考虑以为根的子树, 最早完成作业的时间. 转移为 , 表示的儿子的集合, 表示之间边的权值)然后第二次 dfs 换根求答案,设当前点为 ,他的父亲为 ,如果,那么,(因为边权非负),也就是说不会出现重复走一条边的情况所以再令即可,修改也可以在的时间内完成,总时间复杂度为, 为询问的数量。

AC code

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+5;
int head[maxm],nt[maxm<<1],to[maxm<<1],idx[maxm<<1],cnt;
int d[maxm];
int a[maxm];
int e[maxm];
int n,q;
void add(int x,int y,int z){
    cnt++;nt[cnt]=head[x];head[x]=cnt;to[cnt]=y;idx[cnt]=z;
}
void dfs1(int x,int fa){
    d[x]=a[x];
    for(int i=head[x];i;i=nt[i]){
        int v=to[i],w=e[idx[i]];
        if(v==fa)continue;
        dfs1(v,x);
        d[x]=min(d[x],d[v]+w);
    }
}
void dfs2(int x,int fa){
    for(int i=head[x];i;i=nt[i]){
        int v=to[i],w=e[idx[i]];
        if(v==fa)continue;
        d[v]=min(d[v],d[x]+w);
        dfs2(v,x);
    }
}
void cal(){
    dfs1(1,1);
    dfs2(1,1);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans^=d[i];
    }
    printf("%d\n",ans);
}
void solve(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<n;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,i);
        add(y,x,i);
        e[i]=z;
    }
    while(q--){
        int op;scanf("%d",&op);
        if(op==1){
            int x,y;scanf("%d%d",&x,&y);
            a[x]=y;
        }else if(op==2){
            int x,y;scanf("%d%d",&x,&y);
            e[x]=y;
        }else{
            cal();
        }
    }
}
signed main(){
    solve();
    return 0;
}

码农公寓

2022—SWJTU-寒假ACM校队选拔赛第二场-题解

A - *楼梯

算法分析

AC code

B - cold爱吃小蛋糕

算法分析

AC code

C - 郑老板玩方块

算法分析

AC code

D - 风神瞳

算法分析

AC code

E - cold不会字符串

算法分析

AC code

F - 你一定会种树吧2.0

算法分析

AC code

G - 郑老板爱玩博弈论

算法分析

AC code

H - 琴

算法分析

AC code

I - 简单数学2.0

算法分析

AC code

J - 简单水题

算法分析

AC code

K - 学不会的知识

算法分析

AC code

L - 写不完了

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

算法分析

AC code

相关文章