算法馬拉松24

算法馬拉松24

A?小C的多邊形

• 題意：

n+1個點的多邊形。給外圈的邊標記上1~n，里圈的邊也標記上1~n，使得對于一個外圈相鄰點與中間點構成的三角形的邊權之和都相等。\(n \le 10^6\)

• 題解：

顯然每個三角形權值和為\(\frac{3(n+1)}{2}\)

一開始簡化成n個數排一個環，相鄰兩個數的和不相等并且有上下界，然后并不好做

構造了一下n=5發現外圈正好1..5，內圈1,2之間填n

然后這樣寫一下交上就T了...不加輸出優化tle 2333

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;char c[20];
inline void put(int x) {int p = 0;while(x) c[++p] = x%10 + '0', x /= 10;while(p) putchar(c[p--]);
}
int n;
void solve() {for(int i=1; i<=n; i++) put(i), putchar(' ');puts("");int sum = (n+1)/2*3-1, now = (n+3)/2-1;for(int i=1; i<=n; i++) {put(now); putchar(' ');now = sum - now;sum--;}
}
int main() {
//  freopen("in", "r", stdin);scanf("%d", &n); n--;if(~n&1) puts("0");else solve();
}

---

B?逆序對統計

• 題意：

n個位置，\(1..m\)中每個數可以放在某一個位置，求逆序對最多個數。\(n \le 20, m \le 100\)

• 題解：

比賽時幾乎想到正解了qwq

從小到大枚舉數，然后放一個數只會與他位置后面的數構成逆序對，把n狀壓一下就行了

但當時認為如果位置i已經有數了，還要減去位置i已經構成的逆序對個數，沒法維護

其實完全不用考慮有數的情況，加入再刪除和沒加入是一樣的，從沒數的狀態可以轉移呀

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 105, M = (1<<20) + 5, INF = 1e9;
inline int read(){char c=getchar(); int x=0,f=1;while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int n, m, a[N], all, one[M], f[2][M], cur;
void print(int x) {for(int i=n-1; i>=0; i--) printf("%c", (x & (1<<i)) ? '1' : '0'); puts("");
}
int main() {freopen("in", "r", stdin);n=read(); m=read();for(int i=1; i<=m; i++) a[i] = read() - 1;all = 1<<n;for(int i=0; i<=n; i++) one[1<<i] = 1;for(int i=1; i<all; i++) one[i] = one[i&-i] + one[i^(i&-i)];memset(f, -1, sizeof(f));f[cur][0] = 0;for(int i=0; i<m; i++, cur ^= 1) { int *g = f[cur], *d = f[cur^1];for(int s=0; s<all; s++) if(g[s] != -1) { //printf("f %d %d  %d\n", i, s, g[s]); print(s);d[s] = max(d[s], g[s]);if(~ s & (1<<a[i+1])) {int ns = s | (1<<a[i+1]); d[ns] = max(d[ns], g[s] + one[ns >> (a[i+1] + 1)]);}g[s] = -1;}}printf("%d\n", f[cur][all-1]);
}

---

C?俄羅斯方塊

• 題意：

\(n * m \le 10^7\)的01網格，每次將一個俄羅斯方塊區域異或，問是否能全0.

• 題解：

稍微玩一下發現可以做到：

1. 異或兩個相鄰格
2. 將一個1格任意移動

這樣的話1的個數為奇數一定可行啊！

然而我忽略了網格大小，至少要是2*3才行！

這樣的話特判一下2*2 和1*x

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1e7+5;
inline int read(){char c=getchar(); int x=0,f=1;while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}int n, m, a[N];
char s[N];
int main() {freopen("in", "r", stdin);int T = read();while(T--) {n = read(); m = read();if(n == 1 || m == 1) {if(n == 1) {scanf("%s", s+1); n = m; for(int i=1; i<=n; i++) a[i] = s[i] - '0';}else for(int i=1; i<=n; i++) a[i] = read();int flag = 1;for(int i=1; i<=n; i++) if(a[i]) {if(i+3 > n) {flag = 0; break;}for(int j=i; j<=i+3; j++) a[j] ^= 1;}puts(flag ? "Yes" : "No");continue;}int cnt = 0;for(int i=1; i<=n; i++) {scanf("%s", s+1);for(int j=1; j<=m; j++) cnt += (s[j] - '0') & 1;}if(n > m) swap(n, m);if(n >= 2 && m >= 3) puts((cnt & 1) ? "No" : "Yes");else if(n == 2 && m == 2) puts(cnt == 4 || cnt == 0 ? "Yes" : "No");}
}

---

D 單獨寫了 E F棄療