信息工程大学第五届超越杯程序设计竞赛题解

$\huge{信息工程大学第五届超越杯程序设计竞赛}$

写在前面

本篇题解按照题目难易顺序进行排序

大致难易顺序为：A<M<F<D<C<E<G<K<H<B<I<J

A. 遗失的旋律

这道题其实不是一道签到题，但是数据范围~~太水了~~比较友好（可能是为了适应校赛难度），暴力就可以过，所以就成了一道签到题。

题意

给定一个长度为 $n$ 的 $01$ 串 $s$ ，代表两种操作：

$0$ 代表：x++;
$1$ 代表：x *= 2;

然后给定m次询问，对应两种情况：

$o p y$ ：翻转 $s [y]$ 。
$o p x l r$ 以 $x$ 为初始值，执行 $s [l, r]$ 区间的操作，并返回结果。

思路

暴力…

标程

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

const int N = 1e6+5;
int mod = 998244353;

void solve() {
	int n,m; cin >> n >> m;
	string s; cin >> s;
    int res = 0, le = 0, re = 0;
    
    while(m -- ) {
        int op; cin >> op;
        if(op == 1) {
            int y; cin >> y; y --;
            if(s[y] == '1') s[y] = '0';
            else s[y] = '1';
        } else {
            int x, l, r; cin >> x >> l >> r;
            l --,r --;
            for(int i = l ; i <= r; i++) {
                if(s[i] == '0') x += 1;
                else x = x * 2;
                x = x % mod;
            }
            cout << x << endl;
        }
    }
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1;
// 	cin >> T;
	while(T--) solve();
	return 0;
 }

M. Monika’s game

题意

给定一个整数 $x$ ，然后可以操作若干次，每次可以将 $x$ 拆分为不为零的两个数，然后总分会加上拆分的较大数，求最多能加多少分

思路

每次都将 $x$ 拆分为 $1$ 和 $x - 1$ ，结果为： $1+2+3...+n-1=n\times\frac{n-1}{2}$ 。

标程

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

void solve()
{
	int n; cin >> n;
	n --;
	cout << (n * n + n) / 2 << '\n';
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1; 
    cin >> T;
	while(T--) solve();
	return 0;
 }

F. 不规则的轮回

题意

给定 $n$ 个数对，对于每个数对$ (x,y) $会持续执行以下操作直到 $x = y$ ：

当 $x > y$ 时， $x = x - y$
当 $x < y$ 时， $y = y - x$

同时有 q 次询问，每次给定一个数对 $x_q,y_q$ , 问上述给定的 n 个数对的执行过程中出现了 $x q, y q$ 的次数。

思路

模拟，然后用一个二维数组记录，然后 $O (1)$ 查询。

标程

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"
using namespace std;
const int mod=1000000;
const int N = 1e4+5;
int a[N],b[N],c[N][N];
void solve() {
	int n,m,l,r; cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; 
	for(int i=1;i<=n;i++){
		int aa=a[i],bb=b[i];
		c[aa][bb]++;
        while(aa!=bb){
			if(aa>bb){
                aa -= bb;
			}else if(aa<bb){
                bb-=aa;
            }
            c[aa][bb]++;
		}
	}
	cin>>m;
	while(m--){
		cin>>l>>r;
		cout<<c[l][r]<<endl;
	}
	return ;
}
signed main (void)
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T = 1;
	//cin >> T;
	while(T--) solve();
	return 0;
 }

D. 实验室有多少人

题意

给出 $n$ 次记录，每次记录有两个数组 $a, b$ ，代表当前有一个人从 $a$ 时刻来， $b$ 时刻离开；求实验室最多有多少人。

$1\le n\le 1\times10^6$ $1\le x,y\le 1\times10^9$

思路

跟据数据范围，这道题如果采用差分标记区间的方法，必然会导致超时。

跟据 $n$ 的范围，我们考虑在 $O (n l o g n) or O (n)$ 的时间复杂度解决。

$n$ 组数分别有 $n$ 个数字代表某个人在当前时刻来， $n$ 个数字代表这个人在当前时刻离开。

因此我们需要将这 $2 n$ 个数字存起来，排序，然后遍历并记录最多人数。

关键在于排序：按照时间升序排列，相同时间来的人排在前面。

标程

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

const int N = 1e6+5;
int arr[N];
#define PII pair<int, int>

bool cmp(PII n1, PII n2) {
    if(n1.first == n2.first) return n1.second < n2.second;
        return n1.first < n2.first;
}

void solve() {
	int n; cin >> n;
    vector<PII> a;
    for(int i = 1; i <= n; i ++ ) {
        int x, y; cin >> x >> y;
        a.push_back({x, 1});
        a.push_back({y, 2});
    }
    sort(a.begin(), a.end(), cmp);
    
    int mx = 0, x = 0;
    for(PII n1 : a) {
        if(n1.second == 1) x ++;
        else x --;
        mx = max(mx, x);
    }
    
    cout << mx << endl;
}

signed main (void) {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T = 1;
//	cin >> T;
	while(T--)solve();
	return 0;
 }

C. 财政大臣

题意

给出一棵有 $n$ 个节点的树( $1, 2, 3, ..., n$ )，父节点的变化将会影响所有子节点，然后给出父节点的变化，求最后所有节点的值。每个节点都给的有初始值，然后根节点为 $1$ 。

思路

跟据题意可知，每个节点的结果都是：父节点带来的变化+自身的变化+自身的初始值。

因此我们将所有变化用数组存起来，然后遍历整棵树，计算变化值，最后输出时加上初始值。

标程

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

const int N = 1e5+5;
vector<int> a[N];
int b[N], c[N];	//b数组记录初始值，c数组记录变化值

void bianli(int x) {
    if(a[x].empty()) return;
    for(auto i : a[x]) {
        c[i] += c[x];
        bianli(i);
    }
}

void solve() {
	int n, m; cin >> n >> m;
    for(int i = 1; i < n; i ++ ) {
        int x, y; cin >> x >> y;
        a[x].push_back(y);
    }
    for(int i = 1; i <= n; i ++ ) cin >> b[i];
    
    while(m -- ) {
        int op, x, y; cin >> op >> x >> y;
        if(op == 1) c[x] += y; 
        else c[x] -= y; 
    }
    bianli(1);
    
    for(int i = 1; i <= n; i ++ ) 
        cout << b[i] + c[i] << " \n"[i == n]; 
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1;
// 	cin >> T;
	while(T--) solve();
	return 0;
}

E. 在雾中寻宁静

题意

给出一棵有 $n$ 个节点的树( $1, 2, 3, ..., n$ )，然后给节点染色，同时该节点的子节点都会染成该颜色。最后输出每个节点的颜色。每个节点的初始颜色为 $0$ ，然后根节点为 $1$ 。

思路

与F题类似，本题需注意前面染的颜色可能会被后面的颜色覆盖。因此本题只需在记录染色操作时记录下先后顺序，记录顺序也非常简单，用二元组。

标程

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

const int N = 2e5+5;
vector<int> a[N];
pair<int, int> c[N];

void bianli(int x) {
    if(a[x].empty()) return;
    for(auto i : a[x]) {
        if(c[i].second < c[x].second) //判断是否再此之后染色
            c[i] = c[x];
        bianli(i);
    }
}

void solve() {
	int n; cin >> n;
    for(int i = 1; i < n; i ++ ) {
        int x; cin >> x;
        a[x].push_back(i + 1);
    }
    int m; cin >> m;
    for(int i = 1; i <= m; i ++ ) {
        int x, y; cin >> x >> y;
        c[x].first = y;
        c[x].second = i;	//记录顺序
    }
    bianli(1);
    
    for(int i = 1; i <= n; i ++ ) 
        cout << c[i].first << " \n"[i == n]; 
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1;
// 	cin >> T;
	while(T--) solve();
	return 0;
}

G.完美数字

题意

给定 $n, k$ ，然后给出 $n$ 个整数，要求计算 $n$ 个整数中，乘积尾数有 $k$ 个以上的 $0$ 的序列区间个数。

思路

首先，我们需要知道一串数中序列乘积有几个0，这是怎么计算的？

我们发现，所有乘积尾数中包含0的数中，其因子必然有2和5。

因此，我们需要统计序列中每个数字是由多少个 $2$ 和多少个 $5$ 相乘得到。

由于下面要求区间是否符合条件，我们可以将 $2$ 和 $5$ 的个数用前缀和维护。

那么，区间中所有数相乘后尾数 $0$ 的个数即为： $min(sum_2, sum_5)$ 。

最后，若当前区间符合条件，那么当前区间继续延申当然也符合条件。

标程

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

const int N = 2e5 + 5;
int a[N], a2[N], a5[N],b2[N],b5[N];

void check(int x,int i) {
    int t = x;
    while(t % 2 == 0) t /= 2, a2[i] ++;
    t = x;
    while(t % 5 == 0) t /= 5, a5[i]++;
}

void solve()
{
	int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        check(a[i],i);
    }
    
    for(int i = 1; i <= n; i ++ ) {
        b2[i] = b2[i-1] + a2[i];
        b5[i] = b5[i-1] + a5[i];
    }
    
    int res = 0;
    for(int l=0;l<=n;l++) {
    	for(int r = l + 1; r <= n; r ++) {
    		int t2 = b2[r] - b2[l];
	    	int t5 = b5[r] - b5[l];
	    	int sum = min(t2, t5);
	    	if(sum >= k) {
	    		res += n - r + 1;
	    		break;
			}
		}
	}
    cout << res << endl;
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1;
// 	cin >> T;
	while(T--) solve();
	return 0;
}

K.天使的拼图

题意

给出一个图形，然后给出若干组矩形的边长，问是否能由该图形刚好填充这个矩形。

思路

跟据题目提供的图形，我们可以拼出图二 $3\times4$ 大小的矩形。

试一试可知只能拼成如图三图四这种图形。
在这里插入图片描述

标程

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

void solve(){
    int n,m;cin>>n>>m;
    if(n<m)swap(n,m);
    if((n%3==0&&m%4==0)||(n%4==0&&m%3==0)||((n%12==0)&&m>=7)||((m%12==0)&&n>=7))puts("Yes");
    else puts("No");
}

signed main (void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T = 1;
// 	cin >> T;
	while(T--) solve();
	return 0;
}

H.春天与花儿

题意

给出一个长度为 $n$ 的序列，我们可以对序列进行操作：

选择一个数，将其加一。

给出一个数字 $k$ ，问至少操作几次可以让序列的乘积变为其倍数。

思路

标程(暴力)

标程（DFS）

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

int i,j,k,m,n,t,res,a[66];

bool chk(){
	if(a[0])return 1;
	int sb=1;
	for(i=1;i<m;i++){
		for(j=1;j<=min(m-1,a[i]);j++)sb*=i;
		sb%=m;
	}
	if(!sb)return 1;
	return 0;
}

void dfs(int dep){
	if(dep>res)return;
	if(chk()){
		res=min(res,dep); return;
	}
	int i,j,k;
	for(i=1;i<m;i++)if(a[i]){
		j=(i+1)%m;
		a[i]--; a[j]++;
		dfs(dep+1);
		a[i]++; a[j]--;
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m; res=m-1;
	for(i=1;i<=n;i++){
		cin>>k; a[k%m]++;
	}
	dfs(0);
	cout<<res;
}