A
不会
B
不会
C
因为 n = 8 所以我直接选择了暴力
先排个序 然后观察 对于 i 来说 往前 往后 最多能有几个会被传染 记录一下最大最小值就行了
#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N],B[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T = 1; in(T);
while(T--){
in(n);
for(int i = 1;i <= n;i++)
in(A[i]);
sort(A+1,A+n+1);
int mn = n,mx = 0;
for(int i = 1;i <= n;i++){
int cnt = 0,base = A[i];
for(int j = i-1;j >= 1;j--){
if(base - A[j] <= 2) cnt++,base = A[j];
else break;
}
base = A[i];
for(int j = i+1;j <= n;j++){
if(A[j] - base <= 2) cnt++,base = A[j];
else break;
}
cnt++;
mn = min(mn,cnt),mx = max(mx,cnt);
}
cout << mn << ' ' << mx << endl;
}
return 0;
}
D
挺简单的一道题
首先如果斜着走比直着走两次要优 那么肯定是斜着走 反之 就直接直着走
第一种情况下 斜着走完了。肯定会剩下一段大直道 现在考虑 是斜向上 再 斜向下 走 还是 直接向右走两步 好 所以比较下 x 和 y 就行 但要注意 如果要斜着走 必须满足 min(n,m) > 1
#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T = 1; in(T);
ll x,y;
while(T--){
scanf("%d %d %lld %lld",&n,&m,&x,&y);
if(n > m) swap(n,m);
ll ans = 0;
if(2*x >= y){ // 斜着走更好
if(n == 1){
ans += x * (m-1);
}else{ // 斜向上 再 斜向下
ans += y * (n-1);
m -= n;
if(x >= y){ // 斜着走更好
ans += y * (m/2*2);
if(m&1) ans += x; // 最后一步直着走
} else ans += x * m;
}
}else{
ans = x * (n + m - 2);
}
cout << ans << endl;
}
return 0;
}
E
答案很快就能想到是
for i in range(1, t - 3):
boys = t - i
girls = i
ans += C(n, boys) * C(m, girls)
但由于数据过大 所以需要用高精度python
N = 35
fact = []
def init():
fact.append(1)
fact.append(1)
for i in range(2, N):
fact.append(fact[i - 1] * i)
def C(a, b):
if b > a:
return 0
return fact[a] // (fact[b] * fact[a - b])
if __name__ == '__main__':
init()
str = input()
n = int(str.split()[0])
m = int(str.split()[1])
t = int(str.split()[2])
ans = 0
if n < 4 or m < 1:
print(0)
else:
for i in range(1, t - 3):
b = t - i
ans += C(n, b) * C(m, i)
print(ans)
F
阅读理解
只要除第一个字母外 出现了小写字母 就不反转
#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
int A[N];
char str[N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T = 1;
while(T--){
scanf("%s",str);
n = strlen(str);
bool flag = 1;
for(int i = 1;i < n;i++){
if(str[i] >= 'a') flag = 0;
}
if(flag){
for(int i = 0;i < n;i++){
if(str[i] >= 'a') printf("%c",str[i]-('a'-'A'));
else printf("%c",str[i]+('a'-'A'));
}
}else{
for(int i = 0;i < n;i++) printf("%c",str[i]);
}
}
return 0;
}
G
方法一：判断字符串长度
方法二：python
n = eval(input())
if n<= 127:
print("byte")
elif n<=32767:
print("short")
elif n <= 2147483647:
print("int")
elif n<=9223372036854775807:
print("long")
else:
print("BigInteger")
H
不会
I
挺简单的一道线段树 队友写的
#define xx first
#define yy second
#include <bits/stdc++.h>
#define in(x) scanf("%d", &x)
#define lin(x) scanf("%lld", &(x))
#define rep(i, x, y) for(auto i = (x); i <= (y); i ++ )
#define dep(i, x, y) for(auto i = (x); i >= (y); i -- )
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 300010;
const int INF = 0x3f3f3f3f;
const int mo = 1e9 + 7;
struct Node{
int l, r;
int w;
}node[N<<2];
int a[N];
int b;
void pushUp(int rt) {
node[rt].w = node[rt<<1].w + node[rt<<1|1].w;
}
void build(int rt, int l, int r) {
node[rt] = {l, r};
if(l == r) {
return;
}
int mid = l + r >> 1;
build(rt<<1, l, mid);
build(rt<<1|1, mid + 1, r);
}
void add(int rt, int id, int num) {
if(node[rt].l == node[rt].r) {
node[rt].w = num;
return;
}
int mid = node[rt].l + node[rt].r >> 1;
if(id <= mid) {
add(rt << 1, id, num);
} else {
add((rt << 1)|1, id, num);
}
pushUp(rt);
}
int query(int rt, int ql, int qr) {
int l = node[rt].l, r = node[rt].r;
if(ql <= l && qr >= r) return node[rt].w;
int mid = l + r >> 1, sum = 0;
if(ql <= mid) sum = query(rt << 1, ql, qr);
if(qr > mid) sum += query((rt << 1)|1, ql, qr);
return sum;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data/1.in", "r", stdin);
#endif
int m, q; in(m), in(q);
build(1, 1, m);
int idx = 0, last = 0;
rep(i, 1, m) {
in(a[i]);
}
a[0] = 0, a[m + 1] = INF;
rep(i, 1, m) {
if(a[i] <= a[i + 1] && a[i] >= a[i - 1]) {
add(1, ++idx, 0);
} else {
add(1, ++ idx, 1);
}
}
rep(i, 1, q) {
int opt, x, y;
in(opt), in(x), in(y);
if(opt == 1) {
a[x] = y;
rep(j, x - 1, x + 1) {
if(j < 1 || j > m) continue;
if(a[j] <= a[j + 1] && a[j] >= a[j - 1]) {
add(1, j, 0);
} else {
add(1, j, 1);
}
}
} else {
if(x == y) puts("Yes");
else if(x + 1 == y) {
if(a[x] <= a[y]) {
puts("Yes");
} else {
puts("No");
}
} else if(query(1, x + 1, y - 1) == 0) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
J
很明显可以看出第n+1列上的棋子个数跟第1列的棋子个数是一样的 所以我们可以得到两个式子: 和
#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define int ll
#define in(x) scanf("%lld",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 100+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int inv(int x){
return qpow(x,MOD-2);
}
int n,m,k;
int A[N],C[N],times[N],ans[N][2];
int dp[N][N*N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T = 1;
while(T--){
in(n),in(m),in(k);
C[0] = 1; // C(n,0)
for(int i = 1;i <= n;i++){
C[i] = C[i-1] * (n + 1 - i) % MOD * inv(i) % MOD;
}
for(int i = 0;i <= n;i++){ // ai的出现次数
if(m % n >= i) times[i] = m/n+1;
else times[i] = m/n;
}
dp[0][0] = 1;
for(int i = 0;i <= n;i++){ // 贡献
ans[i][1] = qpow(C[i],m/n+1);
ans[i][0] = qpow(C[i],m/n);
}
for(int i = 1;i <= n;i++){
for(int j = 0;j <= k;j++){
for(int t = 0;t <= min(j,n);t++){
dp[i][j] = (dp[i][j] + dp[i-1][j-t] * ans[t][times[i] == (m/n+1)] % MOD) % MOD;
}
}
}
cout << dp[n][k] << endl;
}
return 0;
}
K
不会
L
签到题
输出 min(x,18)就行
M
挺裸的一道拓扑排序题
#include <bits/stdc++.h>
#define pb emplace_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 500+10;
const int M = N<<1;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
int n,m,k;
bool st[N];
int ind[N],out[N];
int h[N],ne[M],e[M],idx;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
ind[b]++,out[a]++;
}
int q[M];
int hh = 0,tt = 0;
void topsort(){
for(int i = '0';i <= 'z';i++)
if(st[i] && !ind[i]) q[tt++] = i;
while(hh != tt){
int t = q[hh++];
char ch = t;
for(int i = h[t]; ~i;i = ne[i]){
int j = e[i];
ch = j;
ind[j]--;
if(!ind[j]) q[tt++] = j;
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T = 1;
while(T--){
memset(h,-1,sizeof h);
in(n);
char str[5];
int a,b,c;
for(int i = 1;i <= n;i++){
scanf("%s",str);
b = str[0],a = str[2],c = str[3];
add(a,b),add(b,c);
st[a] = st[b] = st[c] = 1;
}
int cnt = 0;
for(int i = '0';i <= 'z';i++){
if(st[i]) cnt++;
}
topsort();
if(tt == cnt){
for(int i = 0;i < tt;i++){
char tp = q[i];
printf("%c",tp);
}
} else puts("No Answer");
}
return 0;
}
