A 不断减损的时间

简单题,直接贪心,对于正整数那便是能除就除。负数不操作就行。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
ll sum;
int main() {
	int n = read();
	for(int i = 1;i <= n;i++) {
		int a = read();
		if(a <= 0) sum += a;
		else {
			while(!(a & 1)) a >>= 1;
			sum += a;
		}
		
	}
	cout << sum << endl;
}

B 勉强拼凑的记忆

中档题,关键在于如何构造。alt

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	int T = read();
	while(T--) {
		ll n = read();
		if(n == 1) {
			cout << "1" << endl;
		}
		else if(n == 2) {
			cout << "-1" << endl;
		}
		else {
			ll ans = (n + (n + 1) / 2 * 2) / 3;
			cout << ans << endl;
		}
	}
}

C 忽远忽近的距离

中档题,我的出发点是类似数学归纳,对长度为 4,5,64,5,6 进行归纳,找出这3种长度的解决方法,然后就可以拓展到长度 nn 了,这个见代码。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	int n = read();
	if(n <= 3) {
		cout << "-1" << endl;
		return 0;
	}
	else if(n % 2 == 0) {
		if(n % 4 == 0) {
			for(int i = 1;i <= n / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}			
		}
		else {
			int m = n - 6;
			for(int i = 1;i <= m / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}	
			printf("%d %d %d %d %d %d\n",n - 2,n - 1,n,n - 5,n - 4,n - 3);
		}
	}
	else {
		int m = n - 5;
		if(m == 2) {
			cout << "-1" << endl;	
			return 0;	
		}
		else if(m % 4 == 0) {
			for(int i = 1;i <= m / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}			
		}
		else {
			int mm = m - 6;
			for(int i = 1;i <= mm / 4;i++) {
				int x = i * 4;
				printf("%d %d %d %d ",x - 1,x,x - 3,x - 2);
			}	
			printf("%d %d %d %d %d %d ",m - 2,m - 1,m,m - 5,m - 4,m - 3);
		}
		printf("%d %d %d %d %d\n",n - 1,n,n - 4,n - 3,n - 2);
	}
}

D 宿命之间的对决

简单题,我们假设偶数有先手必胜,那么我就执行必胜方法。那么偶数先手必输,那我就取 22 则还是偶数,出现矛盾,那么其实偶数就一定先手必胜。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
int main() {
	ll n = read();
	if(n % 2 == 0) {
		cout << "kou" << endl;
	}
	else cout << "yukari" << endl;
}

E 公平守望的灯塔

简单题,可以考虑旋转坐标,注意精度问题,用向量表达。

using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
	int x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const long double pi = acos(-1);
ll xa,ya,xb,yb;
int main() {
	cin >> xa >> ya >> xb >> yb;
	long double vecx = (xb - xa) / sqrt(2);
	long double vecy = (yb - ya) / sqrt(2);
	long double x = cos(pi/4) * vecx + sin(pi/4) * vecy + xa;
	long double y = -sin(pi/4) * vecx + cos(pi/4) * vecy + ya;
//	cout << "x :: " << x << " y:: " << y << endl;
	ll ansx = (x + 0.5);
	ll ansy = (y + 0.5);
	if((ansx-xa)*(ansx-xa) - (ansy-yb)*(ansy-yb) == (ansx-xb)*(ansx-xb) - (ansy-ya)*(ansy-ya)) {
		cout << ansx << " " << ansy << endl;
		return 0;
	}
	x = cos(-pi/4) * vecx + sin(-pi/4) * vecy + xa;
	y = -sin(-pi/4) * vecx + cos(-pi/4) * vecy + ya;
	ansx = (x + 0.5);
	ansy = (y + 0.5);
	if((ansx-xa)*(ansx-xa) - (ansy-yb)*(ansy-yb) == (ansx-xb)*(ansx-xb) - (ansy-ya)*(ansy-ya)) {
		cout << ansx << " " << ansy << endl;
		return 0;
	}
	cout << "No Answer!" << endl;	
}

F 迎接终结的寂灭

签到题。输出 4242 就可以。

G 严肃古板的秩序

中档题,比较简单的搜索,可以小剪枝,考虑到每一个数字最多也只能增加该数字这么多,因为取模一定小于他。所以用后缀和剪枝,爆搜即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
ll a[100],b[100],c[100],tot,top;
ll ksm(ll x,ll mod) {
	ll ans = 1,a = x % mod;
	for(;x;x >>= 1,a = a * 1ll * a % mod) {
		if(x & 1) ans = ans * 1ll * a % mod;
	}return ans;
}
bool dfs(int u,ll sum) {
//	cout << u << " " << sum <<" "<< ksm(sum,a[u]) << endl;
	if(u == top + 1) {
		if(sum == tot) return 1;
		else return 0;
	}
	if(sum + c[u] < tot) return 0;
	if(sum > 0 && a[u] > 0)  {
		b[u - 1] = 3;
		if(dfs(u + 1,ksm(sum,a[u]))) return 1;
		b[u - 1] = 0;
	}	
	b[u - 1] = 2;if(dfs(u + 1,sum - a[u])) return 1;b[u - 1] = 0;	
	b[u - 1] = 1;if(dfs(u + 1,sum + a[u])) return 1;b[u - 1] = 0;
	return 0;
}
int main() {
	char ch = getchar();
	while(1) {
		ll x = 0;
		while(isdigit(ch)) {x = x * 10ll + ch - '0';ch = getchar();}
//		cout <<x<<" ? : " << ch << endl;
		a[++top] = x;		
		if(ch == '=') break;
		ch = getchar();
	}
	tot = read();
//	for(int i = 1;i <= top;i++) cout << a[i] << endl;
//	cout << tot << endl;
	
	for(int i = top;i >= 1;i--) c[i] = c[i + 1] + a[i];
	if(dfs(2,a[1])) {
		for(int i = 1;i < top;i++) {
			cout << a[i];
			if(b[i]==1)cout<<'+';
			if(b[i]==2)cout<<'-';
			if(b[i]==3)cout<<'#';
		}
		cout<<a[top]<<"="<<tot<<endl;
	}
	else cout << "-1";
}

H 穿越万年的轮回

留坑。

I 灵魂碎片的收集

中档题,考虑偶数 xx ,由于 x1x-1x3x-3 中有一个是素数。所以对于 x1x-1 我们构造 (x1)2(x-1)^2 ,对于 x3x-3 构造 2(x3)2(x-3) 。那么奇数,我们减去一个因数 11 。考虑到哥德巴赫猜想,所以存在 P1,P2P_1,P_2 使得 x1=P1+P2x-1=P_1+P_2 ,那么构造 P1×P2P_1\times P_2 即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 4e6 + 10;
const ll M = 2e6;
ll a[N],tot,vis[N],p[N];
int main() {
	int T = read();
	vis[1] = 1;
	for(int i = 2;i <= M;i++) {
		if(!vis[i]) {
			p[++tot] = i;
//			cout << i << " ";
		}
		for(int j = 1;j <= tot && p[j] * 1ll * i <= M;j++) {
			vis[p[j] * i] = 1;
			if(i % p[j] == 0) break;
		}
	}
	while(T--) {
		ll x = read();
		if(x == 1) {
			cout << "3" << endl;
			continue;
		}
		if(x == 3) {
			cout << "4" << endl;
			continue;
		}
		if(x == 5 || x == 2) {
			cout << "-1" << endl;
			continue;
		} 
		if(x == 6) {
			cout << "6" << endl;
			continue;
		}
		if(x == 7) {
			cout << "8" << endl;
			continue;
		}
		if(!(x & 1)) {
			if(!vis[x - 1]) {
				printf("%lld\n",(x - 1) * 1ll * (x - 1));
				continue;
			}
			if(!vis[x - 3]) {
				printf("%lld\n",(x - 3) * 2ll);
				continue;
			}
			cout << "-1" << endl;
		}
		else {
			int f = 0;
			for(int i = 2;i <= tot;i++) {
				if((x - 1 > p[i]) && (vis[x - p[i] - 1] == 0) && (x - 1 - p[i] != p[i])) {
					printf("%lld\n",p[i] * 1ll * (x - p[i] - 1));
					f = 1;
					break;
				}
			}
			if(!f) {
				cout << "-1" << endl;
			}
		}
	}
	return 0;
}

J 无法磨灭的悔恨

不会。

K 永恒守候的爱恋

中档题,我们贪心的构造,由于 f(n)=(a1+1)(a2+1)...(ak+1),n=p1a1p2a2...pkakf(n)=(a_1+1)(a_2+1)...(a_k+1),n=p_1^{a_1}p_2^{a_2}...p_k^{a_k} 所以,如果我们从后往前删的话,我们希望删去最大的 aia_i 。如果 f(n)=xf_(n)=x 而每删去一个 aia_i 就会减少 x×aiai+1x\times \frac{a_i}{a_i+1} 。那我们对相同的 aia_i 开一个桶记录,然后等比数列求和即可。

using namespace std;
#define pii pair<int,int>
#define ll long long
ll read() {
	ll x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ? -x : x;
}
const int N = 4e6 + 10;
const int M = 200000;
const int mod = 1e9 + 7;

int n,a[N],b[N];
int ksm(int a,int b) {
	int x = 1;
	for(;b;b >>= 1,a = a * 1ll * a % mod) {
		if(b & 1) x = x * 1ll * a % mod;
	}return x;
}
int inv(int x) {
	return ksm(x,mod - 2);
}
int Sum(int q,int n) {
	int fac = (1 - ksm(q,n) + mod) % mod;
	int ifac = (1 - q + mod) % mod;
	return fac * 1ll * inv(ifac) % mod;
}
int res = 1,ans;
int main() {	
	n = read();
	for(int i = 1;i <= n;i++) {
		a[i] = read();
		res = (a[i] + 1) * 1ll * res % mod;
		b[a[i]]++; 
	}
	for(int i = M;i >= 1;i--) {
		if(b[i]) {
			ans = (ans + res * 1ll * Sum(inv(i + 1) * 1ll * i % mod,b[i]) % mod) % mod;
//			cout << res << endl;
//			res = res * 1ll * inv(i + 1) % mod * (i) % mod;				
			res = res * 1ll * ksm((inv(i + 1) * 1ll * i % mod),b[i]) % mod;
//			cout << res << endl;
			b[i - 1] += b[i];
			b[i] = 0;
		}
	}
	cout << ans << endl;
	return 0;
}