NUC ACM2019级寒假快乐场2020-01-13题解

A - 快乐打雪仗 CodeForces - 1287A

思路：暴力搜索，每个愤怒的学生身前连续个不愤怒的学生人数的最大值即可

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void) {
   
	int t;
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--)
	{
   
		string s;
		int len;
		cin >>len>> s;
		bool flag = false;
		int ans = 0,temp=0;
		for (int i = 0; i < len; i++) {
   
			if (flag) {
   
				if (s[i] == 'A') {
   
					ans = max(ans, temp);
					flag = false;
					temp = 0;
				}
				else {
   
					temp++;
				}
			}
			if (s[i] == 'A') {
   
				flag = true;
			}
		}
		ans = max(ans, temp);
		cout << ans << endl;
	}
	return 0;
}

B - 新年快乐CodeForces - 1283A

计算时间即可

#include<cstdio>
int main(void){
   
    int t;
    scanf("%d",&t);
    while(t--){
   
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%d\n",1440-60*n-m);
    }
    return 0;
}

​

C - 新年礼物 CodeForces - 1283C

思路：将还没有分配的人和还没有被分配的人分别存进两个数组，挨个遍历，如果相同位置是同一个人，就和下一个交换

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int f[maxn];
vector<int> a, b;
bool flag[maxn];
int main(void) {
   
	ios::sync_with_stdio(false);
	int n; cin >> n;//加速
	for (int i = 1; i <= n; i++){
   
		cin >> f[i]; flag[f[i]] = true;
	}
	for(int i=1;i<=n;i++){
   
		if (f[i] == 0)
			a.push_back(i);
		if (flag[i] == false) 
			b.push_back(i);
	}
	int len = a.size();
	for (int i = 0; i <len; i++) {
   
		if (a[i] == b[i]) {
   
			int x = i, y = (i + 1) % len;
			swap(b[x], b[y]);
		}
	}
	for (int i = 0; i <len; i++)
		f[a[i]] = b[i];
	for (int i = 1; i <= n; i++)
		cout << f[i] << ' ';
	return 0;
}

D - 串串门CodeForces - 1244B

思路：正向扫一遍，反向扫一遍。记录走到每个可以上下（为1）的格子经历房间数的最大值，然后*2输出就好，注意边界条件

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
string s;
int main(void) {
   
	long long t, n;
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--)
	{
   
		cin >> n;
		long long ac = 0,temp=0;
		cin >> s;
        //正向扫
		for (int i = 0; i <n; i++)
		{
   
			if (s[i] == '1') {
   
				ac = i + 1;
			}
		}
        //反向扫
		for (long long i = 0; i<n; i++)
		{
   
			if (s[n-i-1] == '1') {
   
				ac = max(ac, i+1);
			}
		}
        //没出现1时，答案为n，ac为0，则输出n
		cout << max(2 * ac,n) << endl;
	}
	return 0;
}

E - Everyone is a freaking Winner!

CodeForces - 1263C

思路:整除分块裸题，简单来说就是问你有多少个连续区间l，r，其中l到r的值相等

两种方法，第一种就是直接利用整除分块结论，具体讲解看[这里][https://blog.csdn.net/beautiful_CXW/article/details/83143756]

#include <iostream>
#include <set>
using namespace std;
int main(void) {
   
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
   
		int n;
		cin >> n;
		set <int> s;
		s.insert(0);
		for (int i = 1; i*i <= n; ++i) {
   
			s.insert(i);
			s.insert(n / i);
		}
		cout << s.size() << endl;
		for (auto i = s.begin(); i != s.end(); ++i) {
   
			cout << *i << " ";
		}
		cout << endl;
	}
	return 0;
}

还有一种就是暴力查找区间，普通暴力会超时，采用二分暴力即可

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n;
int main(void) {
   
	int t;
	cin >> t;
	while (t--) {
   
		
	vector<long long>ans;
	cin >> n;
	int x = 1;
	ans.push_back(n);
	while (x <= n) {
   
		long long l = x, r = n + 1, temp = l;
		long long d = n / l;
		while (l <= r) {
   
			long long mid = (l + r)>>1;
			if (n / mid == d) {
   
				l = mid + 1;
				temp = mid;
			}
			else {
   
				r = mid - 1;
			}
		}
		ans.push_back(n / (temp + 1));
		x = temp + 1;
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++) {
   
		cout << ans[i] << " ";
	}
	cout << endl;
	}
	return 0;
}

F - 韩美美的文具CodeForces - 1244A

简单题，模拟就OK了

#include<iostream>
#include<cstdio>
using namespace std;
int main(void) {
   
	long long t;
	cin >> t;
	while (t--) {
   
		long long a, b, c, d, k;
		ios::sync_with_stdio(false);
		cin >> a >> b >> c >> d >> k;
		long long a1 = a / c;
		if (a%c != 0)
			a1++;
		long long a2 = b / d;
		if (b%d != 0)
			a2++;
		if (a1 + a2 > k) {
   
			cout << "-1" << endl;
		}
		else
			cout << a1 << " " << a2 << endl;
	}
	return 0;
}

G - 如果想过个好年别碰这道题 UVA - 227

经典1993年World Finals大模拟。。。

思路：主要考点为数据的输入，指令的输入和结果的输出，用来练习输入输出非常不错。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char puzzle[10][10];
int main(void){
   
	int kase = 0;
	while (fgets(puzzle[0], 7, stdin)){
    //读入每行的5个字符加换行
		if (puzzle[0][0] == 'Z') 
			break;
		for (int i = 1; i < 5; ++i)
			fgets(puzzle[i], 7, stdin);
		int ei = 0, ej = 0; //找出空的那个格子
		for (int i = 0; i < 5; ++i)
			for (int j = 0; j < 5; ++j)
				if (puzzle[i][j] == ' '){
   
					ei = i, ej = j;
					break;
				}
		bool valid = true; //标志非法指令出现过
		char moves[101];
		int cnt = 0;
		char c;
		while (cin >> c && c != '0') //考虑隔行读入
			moves[cnt++] = c;
		int ni = ei, nj = ej;
		for (int i = 0; i < cnt; ++i)
		{
   
			switch (moves[i])
			{
   
			case 'A': ni = ei - 1; nj = ej; break;
			case 'B': ni = ei + 1; nj = ej; break;
			case 'L': nj = ej - 1; ni = ei; break;
			case 'R': nj = ej + 1; ni = ei; break;
			default: break;
			}
			//非法情况:
			if (ni < 0 || ni > 4 || nj < 0 || nj > 4)
			{
   
				valid = false;
				break;
			}
			else
			{
   
				swap(puzzle[ei][ej], puzzle[ni][nj]);
				ei = ni, ej = nj; //更新空格位置
			}
		}
		getchar(); //吞掉指令结束符0后面的回车
		if (kase++) cout << endl; //非首个测试前输出换行
		cout << "Puzzle #" << kase << ":\n";
		if (valid == false)
			cout << "This puzzle has no final configuration." << endl;
		else {
   
			for (int i = 0; i < 5; ++i) {
   
				for (int j = 0; j < 4; ++j)
					cout << puzzle[i][j] << ' ';
				cout << puzzle[i][4] << endl;
			}
		}
	}
	return 0;
}

H - 幸运数POJ - 3696

思路

因为M全部由8组成，即
$$M=（10^x-1）\ast 8/9=k\ast N$$

$$(10^x-1)\ast 8/gcd(8,N)=9\ast k\ast N/gcd(8,N)$$

$$令p=8/gcd(8,N);q=9\ast N/gcd(8,N)$$

则有
$$(10^x-1)\ast p=k\ast q$$
由于p和q互质，则
$$(10^x-1)\%q==0$$
根据同余定理可知
$$10^x\equiv 1（modq）$$
根据欧拉定理可知
$$当gcd(a,b)==1时，a^{\phi }(b)\equiv 1(modb);$$
即可得出：
$$

当gcd(10,q)==1时 10^φ(q)≡1(mod q) 即通过枚举φ(q)的因子（最小因子）就能得出结果
$$
由于N比较大，因此采用long long 型。同时做一个素数表。
在进行幂求模运算的时候可以采用快速幂的方法。
由于在进行快速幂求模的时候数据会爆long long ，因此要进行优化。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, mod;
int Case;
ll gcd(ll a, ll b)
{
   
	return a % b == 0 ? b : gcd(b, a%b);
}
ll Er(ll x)//欧拉函数
{
   
	ll re = x;
	for (ll i = 2; i*i <= x; i++)
	{
   
		if (x%i == 0)
		{
   
			re = re / i * (i - 1);
			while (x%i == 0) x /= i;
		}
	}
	if (x > 1) re = re / x * (x - 1);
	return re;
}
ll mul(ll a, ll b, ll p)//优化取模乘法
{
   
	ll re = 0;
	while (b)
	{
   
		if (b & 1) re = (re + a) % p;
		a = 2 * a%p;
		b >>= 1;
	}
	return re;
}
ll ksm(ll a, ll b, ll p)//快速幂
{
   
	ll re = 1; a %= p;
	while (b)
	{
   
		if (b & 1) re = mul(re, a, p);
		a = mul(a, a, p); b >>= 1;
	}
	return re;
}
int main(void){
   
	while (scanf("%lld", &n))
	{
   
		if (n == 0) return 0;
		Case++;
		ll d = gcd(n, 8);
		ll phi = Er(9 * n / d);
		mod = 9 * n / d;
		ll flag = 9223372036854775806;
		for (ll i = 1; i*i <= phi; i++)
		{
   
			if (phi%i == 0)
			{
   
				if (ksm(10, i, mod) == 1)
					flag = min(flag, i);
				if (ksm(10, phi / i, mod) == 1)
					flag = min(flag, phi / i);
			}
		}
		flag == 9223372036854775806 ? printf("Case %d: 0\n", Case) : printf("Case %d: %lld\n", Case, flag);
	}
	return 0;
}