这次比赛是原题大战吗
A
顺序枚举没道题目，判断是切掉还是跳过，一直到结束为止，统计出两人分别切了多少题。
时间复杂度
#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
int 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;
}
const int N = 1e6 + 5;
int n , T , m1 , m2 , a[N] , b[N];
signed main() {
n = read() , T = read();
int T1 = T , T2 = T;
m1 = read() , m2 = read();
For(i , 1 , n) a[i]= read();
For(i , 1 , n) b[i] = read();
int ans1 = 0 , ans2 = 0;
For(i , 1 , n) {
if(T1 < a[i] || b[i] >= m1) continue;
++ ans1 , T1 -= a[i];
}
For(i , 1 , n) {
if(b[i] >= m2) {
if(T2 < a[i] * 2) continue;
++ ans2 , T2 -= a[i] * 2;
} else {
if(T2 < a[i]) continue;
++ ans2 , T2 -= a[i];
}
}
printf("%d %d\n" , ans1 , ans2);
return 0;
} B
不难发现因为每个点所连的边所以是不可能出现答案为-1的情况的。
接下来只要对这张图黑白染色，因为必定存在合法方案，所以遇到一个点不合法的时候直接更改他的颜色即可。
时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define For( i , x , y) for(ri i = x ; i <= y; ++ i)
#define lc(x) x << 1
#define rc(x) x << 1 | 1
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;
}
const int N = 1e6 + 5;
int n , tot , head[N] , m , col[N] , used[N];
struct Edge {
int to , nxt;
} e[N << 1];
inline void addedge(int x , int y) {
e[++ tot] = (Edge) {y , head[x]} , head[x] = tot ;
}
inline void dfs(int u) {
int cnt = 0;
for(ri i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].to;
if(!used[v]) {
used[v] = 1 ;
col[v] = col[u] ^ 1;
dfs(v);
}
if(col[v] == col[u]) ++ cnt;
}
if(cnt > 1) col[u] = col[u] ^ 1;
}
int main() {
n = read() , m = read();
For(i , 1 , m) {
int u = read() , v = read();
addedge(u , v) , addedge(v , u);
}
For(i , 1 , n) if(!used[i]) dfs(i);
For(i , 1 , n) printf("%d ", col[i] + 1) ; putchar('\n');
return 0;
} C
区间异或、区间求和。
直接用懒标记修改肯定是不行的。
考虑开20颗线段树分别记录每一个数的每一位，对每颗线段树进行修改和询问即可
时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define For(i , x , y) for(i = x ; i <= y; ++ i)
#define lc(x) x << 1
#define rc(x) x << 1 | 1
const int N = 2e5 + 5;
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 n , T , a[N] , bit[N << 2][21] , lazy[N << 1];
inline void pushup(ll x) {
for(ri i = 20 ; ~i ; -- i) bit[x][i] = bit[lc(x)][i] + bit[rc(x)][i];
}
inline void pushdown(ll x , ll l , ll r) {
if(!lazy[x]) return ;
lazy[lc(x)] ^= lazy[x]; lazy[rc(x)] ^= lazy[x];
int mid = (l + r) >> 1;
for(ri i = 20 ; ~i ; -- i)
if((lazy[x] >> i) & 1) {
bit[lc(x)][i] = mid - l + 1 - bit[lc(x)][i];
bit[rc(x)][i] = r - mid - bit[rc(x)][i];
}
lazy[x] = 0;
}
inline void build(ll rt , ll l , ll r) {
if(l == r) {
ll x = read();
for(ri i = 20 ; ~i ; -- i)
if((x >> i) & 1) bit[rt][i] = 1;
return;
} int mid = (l + r) >> 1;
build(lc(rt) , l , mid);
build(rc(rt) , mid + 1 , r);
pushup(rt);
}
inline void update(ll rt , ll l , ll r , ll L , ll R , ll k) {
if(l == L && r == R ) {
lazy[rt] ^= k;
for(ri i = 20 ; ~i ; -- i)
if((k >> i) & 1) bit[rt][i] = R - L + 1 - bit[rt][i];
return ;
}
pushdown(rt , L , R);
int mid = (L + R) >> 1;
if(r <= mid) update(lc(rt) , l , r , L , mid , k);
else if(l > mid) update(rc(rt) , l , r , mid + 1 , R , k);
else update(lc(rt) , l , mid ,L , mid , k) , update(rc(rt) , mid + 1 , r , mid + 1 , R , k);
pushup(rt);
}
inline ll query(ll rt , ll l , ll r , ll L , ll R ) {
if(l == L && r == R) {
ll res = 0;
for(ri i = 20 ; ~i ; -- i) res += (1 << i) * bit[rt][i];
return res;
} pushdown(rt , L , R);
int mid = (L + R) >> 1;
if(r <= mid) return query(lc(rt) , l , r , L , mid );
else if(l > mid) return query(rc(rt) , l , r , mid + 1 , R);
else return query(lc(rt) , l , mid ,L , mid ) + query(rc(rt) , mid + 1 , r , mid + 1 , R);
}
int main() {
ri i , j;
n = read(); T = read();
build(1 , 1 , n);
while(T --) {
int opt = read() , x = read() , y = read() , z;
if(opt == 1) printf("%lld\n",query(1 , x , y , 1 , n));
else z = read() , update(1 , x , y , 1 , n , z);
}
return 0;
} D
这是个很妙的思维题。
我们发现每次修改过程中左上角的位置是一定会被修改的
总共有三个人，三种颜***r>所以最后只要看左上角的颜色就行了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define For( i , x , y) for(ri i = x ; i <= y; ++ i)
#define lc(x) x << 1
#define rc(x) x << 1 | 1
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;
}
const int N = 1e3 +5;
int T , n , m;
char s[N][N];
int main() {
T = read();
while(T --) {
n = read() , m = read();
For(i , 1 , n) scanf("%s" , s[i] + 1);
if(s[1][1] == 'R') puts("dreagonm");
else if(s[1][1] == 'G') puts("fengxunling");
else puts("BLUESKY007");
}
return 0;
} E
签到题，不赘述
京公网安备 11010502036488号