A - Gold and Silver
最优解竟然是找规律
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; i ++)
const int maxn = 2e5 + 5;
inline ll read()
{
ll t = 0, dp = 1; char c = getchar();
while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
return t * dp;
}
inline void write(ll x){if (x < 0) {putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
int A[maxn], B[maxn];
signed main()
{
int N = read();
For(i,1,N) A[i] = read();
For(i,1,N-1)
{
if (A[i] > A[i + 1])
{
B[i] ++;
B[i + 1] ++;
}
}
For(i,1,N) write_p(B[i] % 2);
return 0;
}
B - Balls of Three Colors
一次只关注一个结果球(设为R球),假定 G $\geq$ B,其中能满足最后都变为红球的必要条件是G ≡ Bmod3,通常最少次数操作是先将非红球个数统一
然后其中有(G - B) / 3次如下操作:
1.将红球和绿球转换成蓝色球
2.将绿球和蓝球转换成红球
3.将绿球和蓝球转换成红球
最后的操作则是统一将绿球和蓝球转换为红球,次数为B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; i ++)
const int MOD = 1e9 + 7;
const int maxn = 2e5 + 5;
inline ll read()
{
ll t = 0, dp = 1; char c = getchar();
while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
return t * dp;
}
inline void write(ll x){if (x < 0) {putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
inline int count(int R, int G, int B)
{
if ((G + B * 2) % 3) return MOD;
else return max(G, B);
}
signed main()
{
int T = read();
while (T --)
{
int R = read(), G = read(), B = read(), ans = min({count(R, G, B), count(G, B, R), count(B, R, G)});
writeln((ans == MOD ? -1 : ans));
}
return 0;
}
C - Max Dot
是个有点难想的贪心,凸包能将O(N*N)降为O(N)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
const int MOD = 1e9 + 7;
const int maxn = 5005;
inline ll read()
{
ll t = 0, dp = 1; char c = getchar();
while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
return t * dp;
}
inline void write(ll x){if (x < 0) {putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
double A[maxn], ans;
signed main()
{
int N = read(); double M, S; scanf("%lf %lf", &M, &S);
For(i,1,N) scanf("%lf", &A[i]);
int cur = N;
while (S > 1e-10)
{
int pos = -1; double ret = 0, sum = 0;
Dow(i,1,cur)
{
sum += A[i];
double tmp = sum / (cur - i + 1);
if (tmp > ret) ret = tmp, pos = i;
}
int len = cur - pos + 1;
double used = min(S / len, M);
For(i,pos,cur)
{
S -= used;
ans += used * A[i];
}
cur = pos - 1;
}
printf("%.15lf\n", ans);
return 0;
}
D - Between Two Arrays
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define For(i,a,b) for (int i = a; i <= b; i ++)
#define Dow(i,a,b) for (int i = b; i >= a; -- i)
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int maxn = 2e5 + 5;
inline ll read()
{
ll t = 0, dp = 1; char c = getchar();
while(!isdigit(c)) {if (c == '-') dp = -1; c = getchar();}
while(isdigit(c)) t = t * 10 + c - 48, c = getchar();
return t * dp;
}
inline void write(ll x){if (x < 0) {putchar('-'); x = -x;} if(x >= 10) write(x / 10); putchar(x % 10 + 48);}
inline void writeln(ll x){write(x); puts("");}
inline void write_p(ll x){write(x); putchar(' ');}
inline void write_b(ll x){putchar(' '); write(x);}
int A[maxn], sum[maxn], dp[maxn], pre, s;
signed main()
{
int N = read();
For(i,1,N) A[i] = read();
sum[1] = dp[1] = 1;
For(i,2,N)
{
if (A[i - 1] == A[i]) pre = i - 1;
sum[i] = (sum[i - 1] + (dp[i] = (sum[i - 1] - (pre ? sum[pre - 1] : 0) - (i > 3 && A[i] != A[i - 1] && A[i] == A[i - 2] && A[i - 1] == A[i - 3] ? (s = (s + dp[i - 3]) % mod) : s = 0) + mod * 2) % mod)) % mod;
if (A[i - 1] == A[i]) pre = i;
}
writeln(dp[N]);
return 0;
}