Educational Codeforces Round 14
A Fashion in Berland
做法:模拟
代码:
void solve(){
int n;
cin >> n;
int ans = 0;
for (int i = 1;i <= n;i ++) {
int x;
cin >> x;
ans += x;
}
if(n == 1) {
if(ans == 1)
cout << "YES" << endl;
else cout << "NO" << endl;
}else if(n > 1) {
if(ans == n - 1) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
B s-palindrome
做法:模拟,前三题都纯模拟 看代码就好了
代码:
bool check(char a,char b) {
if(a == b) {
if(a == 'A' || a == 'H' || a == 'W' || a == 'T' || a == 'Y' || a == 'U' || a == 'I' || a == 'O') return 1;
if(a == 'M' || a == 'V' || a == 'X') return 1;
if(a == 'o' || a == 'w' || a == 'x' || a == 'v') return 1;
return 0;
}
else {
if(a == 'b' && b == 'd') return 1;
if(a == 'p' && b == 'q') return 1;
if(a == 'd' && b == 'b') return 1;
if(a == 'q' && b == 'p') return 1;
return 0;
}
return 0;
}
bool checklast(char a) {
if(a == 'A' || a == 'H' || a == 'W' || a == 'T' || a == 'Y' || a == 'U' || a == 'I' || a == 'O') return 1;
if(a == 'M' || a == 'V' || a == 'X') return 1;
if(a == 'o' || a == 'w' || a == 'x' || a == 'v') return 1;
return 0;
}
void solve(){
string s;
cin >> s;
int n = s.size();
s = " " + s;
bool f = 1;
for (int i = 1;i <= n / 2;i ++ ) {
if(check(s[i] , s[n - i + 1]) == 0) f = 0;
}
if(n & 1) {
if(checklast(s[n / 2 + 1]) == 0) f = 0;
}
cout << ((f == 1) ? "TAK": "NIE") << endl;
}
C Exponential notation
做法:纯纯的模拟,有点恶心,要分小数点的前后来看
代码:
void solve(){
string s;
cin >> s;
int n = s.size();
s = " " + s;
int pos = n + 1;
for (int i = 1;i <= n;i ++) {
if(s[i] == '.') pos = i;
}
if(pos == 0) pos == n + 1;
int stq = -1,sth = -1;
for (int i = 1;i <= n;i ++) {
if(s[i] != '0' && s[i] != '.') {
stq = i;
break;
}
}
for (int i = n;i >= 1;i --) {
if(s[i] != '0' && s[i] != '.') {
sth = i;
break;
}
}
if(stq == -1 && sth == -1) {
cout << 0 << endl;
return;
}
cout << s[stq];
if(stq != sth) cout << '.';
for (int i = stq + 1;i <= sth;i ++) {
if(s[i] == '.') continue;
cout << s[i];
}
if(stq > pos) {
if(stq - pos != 0)
cout << "E-" << stq - pos << endl;
}
else {
if(pos - stq - 1 != 0)
cout << "E" << pos - stq - 1 << endl;
}
}
D Swaps in Permutation
做法:这种排列题想到用图去做是一件很显然的思路,所以其实就是用并查集去维护每一个连通块,把每一个连通分块的数放在堆上,按顺序一个个输出就可以了。
代码:
priority_queue<int> q[N];
int f[N];
int find(int x) {
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
void solve(){
int n , m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1;i <= n;i ++) cin >> a[i], f[i] = i;
for (int i = 1;i <= m;i ++) {
int x, y;
cin >> x >> y;
x = find(x);
y = find(y);
if(x != y) f[x] = y;
}
for (int i = 1;i <= n;i ++) q[find(i)].emplace(a[i]);
// for (int i = 1;i <= n;i ++) cout << find(i) << ' ';
for (int i = 1;i <= n;i ++) {
cout << q[find(i)].top() << ' ';
q[find(i)].pop();
}
cout << endl;
}
E Xor-sequences
做法:很棒的一道矩阵加速加dp题,这道题我一开始做的时候甚至没有想到暴力的递推去做,其实想想是比较显然的,我们可以这么考虑,当前元素是否能放入,那么只和前面一个元素有关,状态可以这么去考虑,\(dp_{i,j}\)为当前放到第\(i\)个位置,放第\(j\)个元素的方案数,那么递推方程为\(dp_{i, j} = \sum_{k = 1}^{n}dp_{i - 1,k}\ast \left [ popcount(a_{k}\bigoplus a_{j} |3) \right ]\)
\(k\)是\(10^{18}\)所以显然这个方程直接去做是超时的,我们可以考虑矩阵加速,因为这个\(popcount\)是可以预处理出来的,做一个矩阵快速幂即可。
代码:
int sz;
struct mat {
int a[115][115];
inline mat() { memset(a, 0, sizeof a); }
inline mat operator-(const mat& T) const {
mat res;
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j) {
res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;
}
return res;
}
inline mat operator+(const mat& T) const {
mat res;
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j) {
res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;
}
return res;
}
inline mat operator*(const mat& T) const {
mat res;
int r;
for (int i = 1; i <= sz; ++i)
for (int k = 1; k <= sz; ++k) {
r = a[i][k];
for (int j = 1; j <= sz; ++j)
res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= mod;
}
return res;
}
inline mat operator^(int x) const {
mat res, bas;
for (int i = 1; i <= sz; ++i) res.a[i][i] = 1;
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j) bas.a[i][j] = a[i][j] % mod;
while (x) {
if (x & 1) res = res * bas;
bas = bas * bas;
x >>= 1;
}
return res;
}
};
const double eps = 1e-8;
// const int M = N * 4;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
void solve(){
int n ,k ;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1;i <= n;i ++) cin >> a[i];
vector<int> f(n + 1);
mat C;
sz = n;
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= n;j ++) {
int x = a[i] ^ a[j];
int cnt = 0;
while(x) {
if(x & 1) cnt++;
x >>= 1;
}
if(cnt % 3 == 0) C.a[i][j] = 1;
}
}
C = C.operator^(k - 1);
int ans = 0;
mat Ori;
for (int i = 1;i <= n;i ++) Ori.a[1][i] = 1;
for (int i = 1;i <= n;i ++) {
for (int j = 1;j <= n;j ++) {
ans = (ans + Ori.a[1][j] * C.a[j][i] % mod) % mod;
}
}
cout << ans << endl;
}
标签:Educational,return,mat,int,void,Codeforces,cin,&&,14
From: https://www.cnblogs.com/zwh-zzz/p/17057536.html