A、Sumo and Keyboard-Cat
直接遍历整个字符串康康多少个地方进行了大小写转换，初始状态为大写，注意一下就过了，签到题。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
#define endl "\n"
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
int main() {
js;
int cnt = 0, op = 0;
string s; cin >> s;
for (auto it : s) {
if (!op and it >= 'a' and it <= 'z') ++cnt, op ^= 1;
else if (op and it >= 'A' and it <= 'Z') ++cnt, op ^= 1;
}
cout << cnt << endl;
return 0;
}
B、Sumo and His Followers
中文题意：给出n个人的接水时间，问如何安排顺序人整体等待时间最小。
经典贪心题，直接排序，耗时小的最先接水，整体等的时间最短。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
#define endl "\n"
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
ll a[N];
int main() {
int T = read();
while (T--) {
int n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + 1 + n);
ll ans = 0;
for (int i = 1; i < n; ++i)
ans += a[i] * (n - i);
printf("%.2f\n", 1.0 * ans / n);
}
return 0;
} C、Sumo and Virus
二维动态规划，题意看出，从得病到发病，这一段人是只有6天的，12天前感染的人今天最后一天有感染性，7天前感染的人第一次有感染性，那么我们用一个二维dp数组分别代表这一天被感染人数和具有感染别人能力的人数，注意整个村子只有m个人，需要判断下最小值。码起来注意细节。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
#define endl "\n"
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
ll dp[2][N]; // dp[0][n] 代表第n天有的有感染力的人，dp[1][n]被感染的人
int main() {
int T = read();
while (T--) {
ll x = read(), m = read(), n = read();
memset(dp, 0, sizeof(dp));
dp[1][1] = 1;
ll cnt = m - 1; //剩下多少人没被感染过
for (int i = 2; i <= n; ++i) {
for (int j = i - 12; j <= i - 7; ++j)
if (j > 0) dp[0][i] += dp[1][j];
dp[1][i] = min(dp[0][i] * x, cnt);
cnt -= dp[1][i];
}
write(dp[0][n]), putchar(10);
}
return 0;
}
F、Sumo and Luxury Car
给出最多n辆车，每次我可以选择大于等于1小于等于n辆车的排列组合，并且需要选择一辆车坐进去，问共有几种方法。
虽然我不能看出来是递推式，总感觉应该是有递推关系的，直觉就让我接了一个杜教……然后就过了。。
因为不太清楚杜教的常数是多大，只敢放前100个答案进去。预处理一下阶乘和逆元，答案等于*j%2C%20i%5Cleq%20n%2Cj%5Cleq%20i "图片标题")
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
typedef long long ll;
#define SZ(x) ((ll)(x).size())
typedef vector<ll> VI;
typedef pair<ll, ll> PII;
const ll mod = 1000000007;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; }
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
// head
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
ll _, n;
namespace linear_seq {
const ll N = 10010;
ll res[N], base[N], _c[N], _md[N];
vector<ll> Md;
void mul(ll* a, ll* b, ll k) {
rep(i, 0, k + k) _c[i] = 0;
rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
for (ll i = k + k - 1; i >= k; i--) if (_c[i])
rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
rep(i, 0, k) a[i] = _c[i];
}
ll solve(ll n, VI a, VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
// printf("%d\n",SZ(b));
ll ans = 0, pnt = 0;
ll k = SZ(a);
assert(SZ(a) == SZ(b));
rep(i, 0, k) _md[k - 1 - i] = -a[i]; _md[k] = 1;
Md.clear();
rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
rep(i, 0, k) res[i] = base[i] = 0;
res[0] = 1;
while ((1ll << pnt) <= n) pnt++;
for (ll p = pnt; p >= 0; p--) {
mul(res, res, k);
if ((n >> p) & 1) {
for (ll i = k - 1; i >= 0; i--) res[i + 1] = res[i]; res[0] = 0;
rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
}
}
rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
if (ans < 0) ans += mod;
return ans;
}
VI BM(VI s) {
VI C(1, 1), B(1, 1);
ll L = 0, m = 1, b = 1;
rep(n, 0, SZ(s)) {
ll d = 0;
rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
if (d == 0) ++m;
else if (2 * L <= n) {
VI T = C;
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
L = n + 1 - L; B = T; b = d; m = 1;
}
else {
ll c = mod - d * powmod(b, mod - 2) % mod;
while (SZ(C) < SZ(B) + m) C.pb(0);
rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
++m;
}
}
return C;
}
ll gao(VI a, ll n) {
VI c = BM(a);
c.erase(c.begin());
rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
}
};
ll jc[1005], inv[1005];
ll C(int n, int m) {
return jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}
int main() {
int T = read();
vector<ll> v;
jc[0] = 1;
for (int i = 1; i <= 100; ++i) jc[i] = jc[i - 1] * i % MOD;
inv[100] = qpow(jc[100], MOD - 2, MOD);
for (int i = 99; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
for (int i = 1; i <= 100; ++i) {
ll ans = 0;
for (int j = 1; j <= i; ++j)
(ans += C(i, j) * j % MOD) %= MOD;
v.push_back(ans);
}
while (T--) {
int n = read();
//输入n ,输出第n项的值 一般大于10项即可出答案，越多越好
printf("%lld\n", linear_seq::gao(v, n - 1));
}
} H、Sumo and Electricity(Easy)
参考zt大佬的题解大佬太顶了
题目意思：有一个发电站功率未知，所以不与这个发电站相连的电站几乎没有存在的意义，只要统计到与它直接相连的即可。
并且把连接的电站，异或和最小，所以按位考虑，如果某一位1的个数大于0的个数那么这个位贡献为1
剩下的暴力求解即可，防止溢出ll，他还开了个__int128，找我要了个输出函数，嘿嘿……
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
inline void write(__int128 x) { if (!x) { putchar('0'); return; } char F[50]; __int128 tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 100005;
inline ll read(){
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
ll w[505];
vector<int> q[505];
int num[35];
int main(){
int n = read(),m = read();
int st;
for(int i = 1 ;i <= n ; ++i){
w[i] = read();
if(w[i] == -1) st = i;//记录未知功耗发电站位置
}
while(m--){
int u = read(),v = read();//建图
q[u].pb(v);
q[v].pb(u);
}
for(int i = 0 ; i < q[st].size() ; ++i){//统计位置功耗发电站直接连接的数的贡献
for(int j = 0 ; j < 32 ; ++j){
num[j] += ((w[q[st][i]]>>j)&1);
}
}
ll cnt = 0;
for(int i = 31 ; i >= 0 ; --i){//计算位置功耗发电站的功耗
cnt = cnt << 1;
if(num[i] > q[st].size() - num[i]) cnt += 1;
}
w[st] = cnt;
__int128 ans = 0;cnt = 0;
for(int i = 1 ; i <= n ; ++i){
cnt += w[i];//所有发电站功耗
for(int j = 0 ; j < q[i].size() ; ++j){
ans += w[i]^w[q[i][j]];//电缆功耗
}
}
write(ans/2);putchar(10);
cout<<cnt<<endl;
} J、Sumo and Balloon
通过三点确定平面方程，再通过点到平面的距离公式算到球的直径径
不知道什么地方C++精度卡死了……一直都是20多的通过率。。pi也定义的acos（-1）
import math L = int(input()) x,y,z = map(int,input().split()) x1,y1,z1 = map(int,input().split()) x2,y2,z2 = map(int,input().split()) x3,y3,z3 = map(int,input().split()) a1=x2-x1;a2=y2-y1;a3=z2-z1 b1=x3-x1;b2=y3-y1;b3=z3-z1 A=a2*b3-a3*b2 B=a3*b1-a1*b3 #注意这个前面带-1，高数老师枯了 C=a1*b2-a2*b1 D = -(A * x1 + B * y1 + C * z1); h = math.fabs(A * x + B * y + C * z + D) / math.sqrt(A * A + B * B + C * C); h /= 2 print(4/3*h*h*h*math.pi/L)
L、Sumo and Coins
给出a个硬币正面向上，b个硬币反面向上，我需要翻次硬币，每次让
硬币翻转一下，问最终硬币全部同面有几种情况。看题面输出。
/* 正 反 a b 假设a>b,我们肯定是选择翻先全部翻a，剩下个b。 b-1 a+1 a+2 b-2 */
你会发现，状态可以转移，就算没有一个b或者没有一个a，都可以通过操作一直翻转换到a>b的情况
而当n是偶数的时候，a可以一直累加到n，并且换到一定的时候，互换a，b，也可以对反面做同样操作一样换到n。
当n是奇数的时候，可能换到b-1，就换不动了。这样就要去特判多出来的那个数，如果起始a大于b，如果a是奇数可以换到，一定是反面向上，无法换到正面向上，因为多了个数出来无法反转着换。
同理b是奇数的时候特判b即可
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
#define endl "\n"
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int N = 1e5 + 7;
int main() {
int T = read();
while (T--) {
int n = read(), a = read(), b = read();
if (n & 1) {
if (a > b) {
if (a & 1) puts("UP");
else puts("DOWN");
}
else {
if (b & 1) puts("DOWN");
else puts("UP");
}
}
else
puts("ALL");
}
return 0;
} 
京公网安备 11010502036488号