Codeforces Round #609 (Div. 2) 题解 Equation Modulo Equality Long Beautiful Integer Domino for Young K Integers
[Time Limit: 3 squad Memory Limit: 256 MB
]
这题做法很多，甚至可以直接暴力判断
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
bool ok(int a) {
for(int i=2; i*i<=a; i++) {
if(a%i == 0) return 1;
}
return 0;
}
bool che(int a, int b) {
return ok(a) && ok(b);
}
int main() {
int d;
scanf("%d", &d);
for(int i=1000000000; i>=d; i--) {
if(che(i, i-d)) return 0*printf("%d %d
", i, i-d);
}
return 0;
}
Modulo Equality
[Time Limit: 3 squad Memory Limit: 256 MB
]
首先 (a[1]) 一定会变成 (b) 中的某个元素，那么就可以枚举 (a[1]) 变成了多少，把这个数确定为 (x)，然后判断合法性并找出所有的 (x)。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e3 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int a[maxn], b[maxn];
int s[maxn];
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=n; i++) scanf("%d", &b[i]);
sort(a+1, a+1+n);
sort(b+1, b+1+n);
int ans = inf;
for(int i=1; i<=n; i++) {
int d = (b[i]-a[1]+m)%m;
for(int j=1; j<=n; j++) s[j] = (a[j]+d)%m;
sort(s+1, s+1+n);
int f = 1;
for(int j=1; j<=n; j++) {
if(s[j] != b[j]) {
f = 0;
break;
}
}
if(f) ans = min(ans, d);
}
printf("%d
", ans);
return 0;
}
Long Beautiful Integer
[Time Limit: 3 squad Memory Limit: 256 MB
]
可以发现最后的数字一定是以 (k) 为循环节一直循环的，那么我们就可以考虑一开始给出数字的前 (k) 位，看用这 (k) 位循环能否更大，如果不能的话，把这 (k) 位数字加一，然后在开始循环。
由于用 (k) 个 (9) 来循环一定是可以的，所以不用担心加一后位数变多的问题。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
char s[maxn], s1[maxn], s2[maxn];
bool ok() {
for(int i=1; i<=n; i++) {
if(s2[i] > s[i]) return true;
if(s2[i] < s[i]) return false;
}
return true;
}
int main() {
scanf("%d%d", &n, &m);
scanf("%s", s+1);
for(int i=1; i<=m; i++) s1[i] = s[i];
for(int i=1, j=1; i<=n; i++) {
s2[i] = s1[j];
j = j%m+1;
}
if(ok()) return 0*printf("%d
%s
", n, s2+1);
for(int i=1; i<=m; i++) s1[i] = s1[i]-'0';
s1[m]++;
for(int i=m; i>=1; i--) {
if(s1[i]>=10) {
s1[i] -= 10;
s1[i-1] += 1;
}
s1[i] += '0';
}
for(int i=1, j=1; i<=n; i++) {
s2[i] = s1[j];
j = j%m+1;
}
printf("%d
%s
", n, s2+1);
return 0;
}
Domino for Young
[Time Limit: 3 squad Memory Limit: 256 MB
]
思维题杀我，但是这题的思路真是太优雅了。
我们把整个图看成一个国际棋盘，国际棋盘是黑白相间的，那么也就是说答案一定是 (min) (黑格子，白格子)，因为我选了较少的那个，另一个我就一定可以找相邻的凑出来。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
int main() {
scanf("%d", &n);
ll ans1 = 0, ans2 = 0;
for(int i=1, x; i<=n; i++) {
scanf("%d", &x);
if(i&1) ans1+=x/2, ans2+=(x+1)/2;
else ans2+=x/2, ans1+=(x+1)/2;
}
printf("%lld
", min(ans1, ans2));
return 0;
}
K Integers
[Time Limit: 3 squad Memory Limit: 256 MB
]
对于一个 (k)，我们操作的规则都是先把 (1-k) 所有数字移动到一块，然后再进行还原。
对于还原过程，是一个很经典的问题，只需要求他的逆序数就可以了，并且这些步数是必不可少的。在每一步操作中，只需要加上 (k) 带来的贡献就可以，那么只要知道 (k) 的位置后面有多少个已经插入的数字就可以了，这一部分可以用树状数组来实现。
那么只要计算出花费最少的步数使 (1-k) 在一块就可以了。
我们把整个序列中，(a[x]<=k) 的位置看成 (s[x]=0)，(a[x]>k) 的位置看成 (s[x]=1)。
那么现在你得到了一个长度为 (n)，(1) 的个数为 (k)，形如 (1、0、0、1、1、0、1、1、0) 的数组，而你想要让所有的 (1) 靠在一块。
令 (p[i]) 为 (s[i]) 的前缀和，那么对于每一个 (s[i]=0)，把这个 (0) 移出去的最少步数是 (min(p[i], k-p[i]))，而你需要的步数就是 (sum s[i])，因为你只要从两侧开始操作，每一个 (0) 都可以用最少的步数移出去并让中间一块全为 (1)。
由于 (k) 高达 (2e5)，所以这部分必须高效的维护，我们发现，我们可以找出第 (frac{k+1}{2}) 个 (1) 在哪里，然后左侧的 (s[i]=0) 的贡献都是 (p[i])，右侧的 (s[i]=0) 的贡献都是 (k-p[i])。而每次只多一个数字，所以这个 (frac{k+1}{2}) 的位置只会往左或者往后移动一个 (1) 或者不动。那么只要用一个 (set) 来维护这个 (1) 的位置，然后维护一下新插入的 (1) 造成的贡献就可以了。
view
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) x & (-x)
#define mes(a, b) memset(a, b, sizeof a)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int maxm = 1e5 + 10;
const ll mod = 1e9 + 7;
const ll INF = 1e18 + 100;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
int n, m;
int cas, tol, T;
set<int> st;
int a[maxn], p[maxn];
ll sum[maxn];
void update(int x) {
for(int i=x; i; i-=lowbit(i)) sum[i]++;
}
ll query(int x) {
if(x==0) return 0;
int ans = 0;
for(int i=x; i<=n; i+=lowbit(i))
ans += sum[i];
return ans;
}
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]), p[a[i]] = i;
ll ans = 0, k = 0;
printf("0 ");
update(p[1]);
st.insert(p[1]);
auto it = st.begin();
for(int i=2; i<=n; i++) {
ans -= min(query(p[i]+1), i-1-query(p[i]+1));
ans += query(p[i]+1);
update(p[i]), st.insert(p[i]);
if(i%2==0 && p[i]<(*it)) ans += abs((*it)-(*(--it)))-1;
if(i%2==1 && p[i]>(*it)) it++;
if(p[i] > (*it)) ans += p[i]-(*it)+1 - query((*it))+query(p[i]+1);
else ans += (*it)-p[i]+1 - query(p[i])+query((*it)+1);
printf("%lld ", ans);
}
return 0;
}