吉首大学第十届“新星杯”大学生程序设计大赛（暨新生网络同步赛）

部分题解 前言

    下午在群里面看到一个同学疯狂宣传这个比赛，处于好奇的态度(他说难度有cf1800)我参赛了，可能真的有cf1800的题目，只是我没做出来，离比赛还有十多分钟的时候到了吉首的OJ，注册了账号，稍稍等待之后进入了比赛，出于习惯开了A题，然后想了几分钟没有思路，然后切出去看榜单，看见有人过了J题，我赶紧开了J题，嗯，是个签到题，但是WA了一发，读题的时候漏掉了一个信息，改了后A了，然后开了C，立方和公式稍微一化简就能找到a和b和n的关系，然后一发A了，接着开了E，一发A，刷了下榜单，看到L过了十多人，第一发处理边界的时候出了问题，后面想了下可以直接O(N)扫过去找到最小的，第三发A了，然后此时我在20名左右(暂时靠前)，于是又回去看A，稍微想了一下然后又写了个公式，然后自己测试都没过，于是我开始直接硬推公式，想了二十多分钟还是没想出来，于是我开始打表找找规律，在反复观察后，我发现了一个规律，但是当时睡意来了，看着面前的屏幕还有外面刺眼的光线，我的眼睛开始疼痛，强忍着，继续记录规律，在二十多分钟后我把规律转化为了公式，然后交上去第一发CE(本地是能跑的)，我把头文件换成了万能头，交上去一发A了，从这一发A之后后面就做的太难受了，接着我开了D，很明显D是一个模拟题，但是一直写不对(写代码细节没写好)，然后转身开了F，感觉是一个博弈论,第一发我直接交了cxy上去，然后过了一半的测试点，接着交了几法rand，没过就没看了，然后这个时候我发现K题有几十人切出来了，于是赶忙去切K，由于我的粗心，计算的时候写反了，贡献了5发罚时，此时已经是四点五十二了，最后转身去开D，在贡献了20发罚时的情况下，在最后的5分钟把D题A了，当时激动的喊了出来(^^)。

A: 学习快速幂

传送门 解题思路：通过打标找规律我们能发现，复杂度从\(2^{i}-1\)开始到\(2^{i}-1+2^{i-1}\)是连续的，然后通过两次求和可以算出公式

\[2^{n-1}\times(2^n-1)+\frac{(2^{n-1}-1)\times2^{n-1}}{2}+len\times(2^k-1)+\frac{len\times(len-1)}{2} (k = log(n),len = max(0,n-2^{k-1}-1)) \]

退出公式后我们就可以直接写代码啦^^ Code:

#include
using namespace std;
#define ll long long
#define mod 1000000007;
int cnt = 0;

ll qpow(ll a, ll b) {
	if(b == 0) {
		return 1%mod;
	}
	cnt++;
	if(b%2 == 1) {
		return (a*qpow(a,b-1))%mod;
	}
	else {
		return (qpow(a,b/2)*qpow(a,b/2))%mod;
	}
}
long long f(int n) {
	long long ans = 0;
	while(n) {
		n/=2;
		ans++;
	}
	return ans;
}
ll cal(ll n) {
	ll ans = (ll)pow(2,n-1) * (ll) (pow(2,n)-1) + ((ll)pow(2,n-1)-1)*((ll)pow(2,n-1))/2;
	return ans;
}
ll cal2(ll k, ll len) {
	ll ans =len * (ll)(pow(2,k)-1) + (len-1LL)*len/2;
	return ans;
}
int main()
{
	int t;
//	for(int i = 0;i < 5; ++i) {
//		cnt = 0;
//		qpow(1,i);
//		printf("%d\n",cnt);
//	}

	scanf("%d",&t);
	int n;
	while(t--) {
		scanf("%d",&n);
		if(n == 0) {
			puts("0");
			continue;
		}
		long long k = f(n);
		ll ans = 0;
		for(ll i = 1;i >str;
	scanf("%s",ch);
	mp['A'] = 1;mp['2'] = 2;mp['3'] = 3;mp['4'] = 4;mp['5'] = 5;mp['6'] = 6;mp['7'] = 7;mp['8'] = 8;mp['9'] = 9;mp['J'] = 10;mp['Q'] = 11;mp['K'] = 12;
	int l = 0, r = 0;
	for(int i = 0,len = strlen(ch);i < len; ++i) {
		if(vis[ch[i]]) {//S.size() &&
			if(i & 1) {
				while(S.size() && S.top() != ch[i]) {
					vis[S.top()] = false;
					r += mp[S.top()];
					S.pop();
				}
			//	r += 2 * mp[ch[i]];
				if(S.size()) {
					r += 2*mp[S.top()];
					S.pop();
				}
			}
			else {
				while(S.size() && S.top() != ch[i]) {
					vis[S.top()] = false;
					l += mp[S.top()];
					S.pop();
				}
				//l += 2 * mp[ch[i]];
				if(S.size()) {
					l += 2 * mp[S.top()];
					S.pop();
				}
			}
			vis[ch[i]] = false;
			continue;
		}
		S.push(ch[i]);
		vis[ch[i]] = true;
	}
	if(l == r) {
		puts("-1");
	}
	else {
		if(l < r) {
			printf("lbg %d\n",r);
		}
		else
			printf("zqc %d\n",l);
	}
}

E: 会长的榜单

传送门 解题思路:这题就是把秒数转化为小时、分钟、秒数进行表示，如果该秒数为0则直接输出0 Code:

#include
using namespace std;
const int N = 20;
int a[N];
int h[N];
int m[N];
int s[N];
int main()
{
	char name[30];
	int n;
	cin>>n;
	cin>>name;
	for(int i = 0;i < n; ++i) {
		cin>>a[i];
		h[i] = a[i] / 3600;
		a[i] -= h[i] * 3600;
		m[i] = a[i] / 60;
		a[i] -= m[i] * 60;
		s[i] = a[i];
	}
	printf("%s ",name);
	for(int i = 0;i < n; ++i) {
		if(h[i] == 0 && m[i] == 0 && s[i] == 0)
			printf("0%c",i ==n-1?'\n':' ');
		else
			printf("%02d:%02d:%02d%c",h[i],m[i],s[i],i ==n-1?'\n':' ');//格式化输出
	}

}

J: 会长数

传送门 解题思路:暴力把数的每一位拿出来判断，并且把这些数的和判断是否是素数，其实满足条件的数只有23 Code:

#include
#include
#include
#include
#include
using namespace std;
bool is_prime(int n) {
    if(n==0 || n== 1)
    return false;
    for(int i = 2;i *i