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 勉强拼凑的记忆
中档题,关键在于如何构造
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 忽远忽近的距离
中档题,我的出发点是类似数学归纳,对长度为 进行归纳,找出这3种长度的解决方法,然后就可以拓展到长度 了,这个见代码。
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 宿命之间的对决
简单题,我们假设偶数有先手必胜,那么我就执行必胜方法。那么偶数先手必输,那我就取 则还是偶数,出现矛盾,那么其实偶数就一定先手必胜。
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 迎接终结的寂灭
签到题。输出 就可以。
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 灵魂碎片的收集
中档题,考虑偶数 ,由于 , 中有一个是素数。所以对于 我们构造 ,对于 构造 。那么奇数,我们减去一个因数 。考虑到哥德巴赫猜想,所以存在 使得 ,那么构造 即可。
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 永恒守候的爱恋
中档题,我们贪心的构造,由于 所以,如果我们从后往前删的话,我们希望删去最大的 。如果 而每删去一个 就会减少 。那我们对相同的 开一个桶记录,然后等比数列求和即可。
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;
}