签到。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int n;
int a[N];
bool used[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for(int i = 1; i <= n; i++) {
if(used[i]) continue;
++ans;
for(int j = i; j <= n; j++) {
if(a[j] % a[i] == 0) used[j] = 1;
}
}
cout << ans;
return 0;
}
由于数据范围很小,暴力枚举即可。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int n;
int a[N], b[N];
char s[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
cin >> s + 1;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
int ans = 0;
for(int i = 1; i <= n; i++) {
if(s[i] == '1') ++ans;
}
for(int i = 1; i <= 5000; i++) {
int tmp = 0;
for(int j = 1; j <= n; j++) {
if(i - b[j] < 0) continue;
int now = i - b[j];
if(now % a[j] == 0) {
if(s[j] == '1') s[j] = '0';
else if(s[j] == '0') {
s[j] = '1';
}
}
}
for(int j = 1; j <= n; j++) {
if(s[j] == '1') ++tmp;
}
// if(i < 10) cout << tmp << '\n';
ans = max(ans, tmp);
}
cout << ans;
return 0;
}
题意:
给出一串数字,现在要给这串数字涂上两种颜色\(1,2\),要求涂色过后从前往后将\(1\)排开,再将\(2\)排开,最终得到一个非递减序列。
思路:
首先序列自动机预处理下一位,然后贪心处理即可。
感性想一下很容易知道染色方案,对于当前位,\(1\)的颜色肯定是下一个最小的值,如果不是则不满足条件;\(1\)染完色过后按同样的方法对\(2\)进行染色,但是起点不同,注意处理一下。
还有一个细节:\(1\)染的颜色的最大值不能超过前面没染颜色的最小值,否则也不满足条件。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int T, n;
char s[N];
int nxt[N][26];
int last[26];
int col[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> n;
cin >> s + 1;
for(int i = 1; i <= n; i++) col[i] = 0;
for(int i = 0; i < 26; i++) last[i] = n + 1;
for(int i = n; i >= 0; i--) {
for(int j = 0; j < 26; j++) nxt[i][j] = last[j];
if(i) last[s[i] - '0'] = i;
}
int start = 0, up = 26;
for(int i = 0, k; i <= n; i = k) {
int jump = 0;
int low = (i == 0 ? 0 : s[i] - '0');
for(int j = low; j < up; j++) {
if(nxt[i][j] <= n) {
k = nxt[i][j];
jump = 1;
break;
}
}
if(jump == 0) break;
col[k] = 1;
start = s[k] - '0';
if(k != i + 1 && up == 26) {
up = s[i + 1] - '0' + 1;
}
}
for(int i = 0, k; i <= n; i = k) {
int jump = 0;
int low = (i == 0 ? start : s[i] - '0');
for(int j = low; j < 26; j++) {
if(nxt[i][j] <= n && !col[nxt[i][j]]) {
k = nxt[i][j];
jump = 1;
break;
}
}
if(!jump) break;
col[k] = 2;
}
int ok = 1;
for(int i = 1; i <= n; i++) {
if(!col[i]) ok = 0;
}
if(!ok) cout << '-' << '\n';
else {
for(int i = 1; i <= n; i++) cout << col[i];
cout << '\n';
}
}
return 0;
}
全局视野来看,并查集搞搞就行,答案就与生成树有关。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, k;
int a[N], b[N];
int f[N], sz[N];
int find(int x) {
return f[x] == x ? f[x] : f[x] = find(f[x]);
}
bool Union(int x, int y) {
int fx = find(x), fy = find(y);
if(fx != fy) {
sz[fy] += sz[fx];
f[fx] = fy;
return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
}
for(int i = 1; i <= n; i++) f[i] = i, sz[i] = 1;
int ans = 0;
for(int i = 1; i <= k; i++) {
if(!Union(a[i], b[i])) ++ans;
}
// int cnt = 0;
// for(int i = 1; i <= n; i++) {
// if(find(i) == i) {
// cnt += sz[i] - 1;
// cout << sz[i] << '\n';
// }
// }
// int ans = n - cnt;
cout << ans;
return 0;
}
题意:
给出一个\(n*m\)的矩形,满足\(n\leq 12,m\leq 2000\),现在你可以对任意一列执行任意次滑动操作。
记\(r_i\)为第\(i\)行的最大值,求\(\sum_{i=1}^nr_i\)最大为多少。
思路:
一开始看作行也可以滑动,然后就写了一个假题= =
一开始我卡在枚举循环位移这里,后面想了下,只有枚举循环位移,才会覆盖到所有情况。
Code
#include <bits/stdc++.h>
#define MP make_pair
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define sz(x) (int)(x).size()
//#define Local
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 12, M = 2000;
int n, m;
int a[N][M];
pii b[M];
void run() {
cin >> n >> m;
vector <int> col(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
col[j] = max(col[j], a[i][j]);
}
}
for (int i = 0; i < m; i++) b[i] = MP(col[i], i);
sort(b, b + m); reverse(b, b + m);
m = min(m, n);
int lim = 1 << n;
vector <vector<int>> w(m, vector<int>(lim));
for (int i = 0; i < m; i++) {
int j = b[i].se;
for (int s = 0; s < lim; s++) {
for (int k = 0; k < n; k++) {
int sum = 0;
for (int p = 0; p < n; p++) {
if (s >> ((p + k) % n) & 1) {
sum += a[p][j];
}
}
w[i][s] = max(w[i][s], sum);
}
}
}
vector <int> dp(lim);
for (int i = 0; i < m; i++) {
vector <int> new_dp(lim);
for (int s = 0; s < lim; s++) {
int other = (lim - 1) ^ s;
for (int sub = other; ; sub = (sub - 1) & other) {
int Max = w[i][sub];
new_dp[s ^ sub] = max(new_dp[s ^ sub], dp[s] + Max);
if (sub == 0) break;
}
}
swap(dp, new_dp);
}
cout << dp[lim - 1] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
int t; cin >> t;
while(t--) run();
return 0;
}
题意:
给出一个长度为\(n,n\leq 2e5\)的序列。
现在可以执行操作:将全部的\(x\)变为\(y\)。
现在问最少多少次操作,使得所有值相同的元素都在同一块中。
思路:
详见代码:
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n, q;
int a[N];
int fir[N], last[N];
int cnt[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
if(fir[a[i]] == 0) fir[a[i]] = i;
}
for(int i = n; i >= 1; i--) {
if(last[a[i]] == 0) last[a[i]] = i;
}
int ans = 0;
for(int i = 1, j; i <= n; i = j + 1) {
j = last[a[i]];
int st = i;
while(i < j) {
++i; j = max(last[a[i]], j);
}
int tmp = 0;
for(int k = st; k <= j; k++) {
if(++cnt[a[k]] > tmp) tmp = cnt[a[k]];
}
ans += j - st + 1 - tmp;
}
cout << ans;
return 0;
}
原文:https://www.cnblogs.com/heyuhhh/p/11530955.html