競賽連結
- 操作:可以把一個數列的兩個數$a_i$指定給$a_j(i\neq j)$
給你原數列 問能不能用上面的方法將數列的總和變成奇數
很顯然的 滿足以下條件就可
- 數列至少要有一個奇數
- 如果數列長度是偶數 則至少還要有一個偶數
不滿足以上條件就無解
複雜度$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
bool ok[2]={false, false};
for(int i = 0; i < n; i++) {
ok[arr[i]&1]=true;
}
if(n&1) {
if(ok[1]) cout << "YES";
else cout << "NO";
}
else {
if(ok[1] && ok[0]) cout << "YES";
else cout << "NO";
}
cout <<endl;
}
return 0;
}
|
有$s$元
可以花費$x(1\le x)$元 拿回$\lfloor\frac{x}{10}\rfloor$元(也就是無條件捨去後的$\frac{x}{10}$)
問最多可以花費幾元
因為當$x>10$的話個位數會被捨去 所以最好的辦法就是每次都支出$10$的倍數
只要不斷花到沒錢就好 記得剩個位數時還能再花光(拿回$0$元)
複雜度$O(T\log_{10}{s})$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
ll a, b=0, ans=0;
cin >> a;
b=a%10; a-=b;
while(a) {
ans+=a;
a/=10;
b+=a;
a=b/10*10; b%=10;
}
ans+=b;
cout << ans << endl;
}
return 0;
}
|
給定字串$s$
$UDLR$代表上下左右
求一最大區間使得區間內的$L$的數量=$R$的數量且$U$的數量=$D$的數量
雷死 這題我想超久 甚至還FST 我是智障==
反正就是先預處理把前綴的數量都先弄出來
然後再爬行一次 用map存”這個數量 最後一次出現的位置”
然後取最大長度
複雜度$O(|s|log|s|)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n;
string s;
map<pii, int> pos;
cin >> n >> s;
vector<pii> arr(n);
pos.clear();
int a=0, b=0, l=1, r=INF;
for(int i = 0; i < n; i++) {
if(s[i]=='L') a++;
if(s[i]=='R') a--;
if(s[i]=='U') b++;
if(s[i]=='D') b--;
arr[i]=mp(a, b);
if(a==0 && b==0) r=min(r, i+1);
}
for(int i = 0; i < n; i++) {
a=arr[i].F, b=arr[i].S;
if(pos[mp(a, b)]) {
if(r-l > i+1-pos[mp(a, b)]) {
l=pos[mp(a, b)];
r=i+1;
}
}
pos[mp(a, b)]=i+2;
}
if(r==INF) cout << -1 << endl;
else cout << l << ' ' << r << endl;
}
return 0;
}
|
有$n$隻怪物 你和對手共同奮戰(?
你的攻擊力是$a$ 對手的攻擊力是$b$
第$i$隻怪物的血量是$h_i$
每回合的發展如下:
- 你總是先攻 打完後換對手
- 要是某個人的攻擊使怪物的血量變為$0$以下 他就拿一分
- 你可以用小手段使對手略過他那次攻擊(也就是你打兩次)
小手段最多只能用$k$次
模擬就好
先計算$a+b$ 只要 $0<$怪物血量$mod(a+b) \le a$ 那你就拿一分
如果$=0$ or $>a$ 那你就用$\lceil \frac{a}{b}\rceil$次小手段 還是拿一分
如果小手段數量不足 對手拿分
複雜度$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
signed main() {
EmiliaMyWife
int n, a, b, k;
ll ans=0;
cin >> n >> a >> b >> k;
multiset<int> nd;
for(int i = 0, s; i < n; i++) {
cin >> s;
s%=(a+b);
if(s<=a && s) {
ans++;
continue;
}
if(s==0) s+=(a+b);
s-=a;
nd.insert(ceil((double)s/a));
}
for(int a: nd) {
if(a>k) break;
k-=a;
ans++;
}
cout << ans << endl;
return 0;
}
|
將各個字元塗色
使得不一樣顏色的字元就能交換
並且bubble sort
問
EV:能否用兩個顏色就滿足條件
HV:用最小的顏色數量滿足條件
這題我賽中沒寫出來 可撥
只要$a_i\le a_j$且$i<j$就不用交換他們
所以只要維護$x$個非嚴格遞增數列就好
這部分由於字元最多只有26種 也就是$x\le 26$ 直接跑一遍就可
然後就塗色
EV的話只要看$x$是否大於2
複雜度$O(n\times (26))$
由於ans陣列會是遞減的 所以其實可以二分搜 複雜度是$O(n\log(26))$ 不過我不是很懂這樣能幹嘛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
signed main() {
EmiliaMyWife
string s; int n;
cin >> n >> s;
vector<int> ans, color(n);
for(int i = 0; i < n; i++) {
if(ans.empty()) ans.pb(s[i]), color[i]=ans.size()-1;
else {
bool ok = true;
for(int j = 0; j < ans.size(); j++) {
if(ans[j]<=s[i]) {
ans[j]=s[i];
color[i]=j;
ok=false;
break;
}
}
if(ok) {
ans.pb(s[i]);
color[i]=ans.size()-1;
}
}
}
cout << ans.size() <<endl;
for(int a: color) cout << a+1 << ' ';
return 0;
}
|
給一棵樹 每個邊有權重
並且會給定$m$筆
每筆會給出$a_j$到$b_j$中經過的邊的權重最小值<
求根據題目給定順序輸出滿足的邊權重
可能無解
這題我覺得比pE水QQ
只要離線處理
先從最大的最小值開始填
只要這個邊沒被填過或者是個邊要被填的數字跟他已經被填過的數字一樣 就填上去
如果發現已經沒有邊可以填了 就無解
要根據題目給定順序輸出 所以每個邊要編號
複雜度$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof i);
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) (x&-x)
#define siz(v) (long long)v.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
const int MAXN = 2e5+9;
vector<int> ans(6000, 1e7);
vector<vector<pii>> edge(6000);
bitset<6000> visited;
bool valid;
bool dfs(int now, int end, int cur) {
if(visited[now]) return false;
visited[now]=true;
if(now==end) return true;
bool ok = false;
for(pii a: edge[now]) {
if(dfs(a.F, end, cur)) {
if(ans[a.S] > 1e6 || ans[a.S]==cur) ans[a.S]=cur, valid=true;
ok=true;
}
}
return ok;
}
signed main() {
EmiliaMyWife
int n, m;
cin >> n;
vector<pii> out(n-1);
for(int i = 0, a, b; i <n-1; i++) {
cin >> a >> b;
edge[a].pb(mp(b, i));
edge[b].pb(mp(a, i));
}
cin >>m;
vector<pair<int, pii>> arr(m);
for(int i = 0; i < m; i++) {
cin >> arr[i].S.F >> arr[i].S.S >> arr[i].F;
}
sort(all(arr)); reverse(all(arr));
bool valids = true;
for(int i = 0; i < m; i++) {
valid=false;
visited.reset();
dfs(arr[i].S.F, arr[i].S.S, arr[i].F);
valids&=valid;
}
if(valids)
for(int i = 0; i < n-1; i++) {
cout << min(ans[i], 1000000) << ' ';
}
else cout << -1;
return 0;
}
|