T1
我们发现 \(1\) 其实根本没有用,只和一个连通块里的 \(0\) 的个数有关,直接 \(dfs\),判断即可。
#include<iostream>
#include<cstring>
using namespace std;
inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
const int N = 110;
int T, n, m, sum, ans;
int a[N][N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
bool vis[N][N];
bool check(int x, int y){
if (x < 1 || x > n || y < 1 || y > m || a[x][y] == -1) return 0;
return 1;
}
void dfs(int x, int y){
if (vis[x][y]) return;
vis[x][y] = 1;
if (a[x][y] == 0) sum++;
for (int i = 0; i < 4; i++){
int nx = x + dx[i], ny = y + dy[i];
if (!check(nx, ny)) continue;
dfs(nx, ny);
}
}
void solve(){
n = read(), m = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
char c; cin >> c;
if (c == 'X') a[i][j] = -1;
else a[i][j] = c - '0';
}
bool flag = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (a[i][j] != -1 && !vis[i][j] && !flag){
flag = 1, sum = 0;
dfs(i, j);
if (sum & 1) ans++;
}else if (a[i][j] != -1 && !vis[i][j] && flag){
cout << "No\n";
ans = 0;
memset(vis, 0, sizeof vis);
memset(a, 0, sizeof a);
return;
}
}
}
cout << (ans == 1 ? "Yes\n" : "No\n");
ans = 0;
memset(vis, 0, sizeof vis);
memset(a, 0, sizeof a);
}
int main(){
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
T = read();
while (T--) solve();
return 0;
}
T2
结论题,不为 \(1\) 的数的个数为奇数个就为 No
,否则就为 Yes
,其实也挺好证明的,这里略。
#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
const int N = 5e5 + 10;
int T, n;
int a[N];
void solve(){
n = read();
int cnt = 0, el;
for (int i = 1; i <= n; i++){
a[i] = read();
if (a[i] == 1) cnt++;
}
el = n - cnt;
if (el & 1) cout << "Yes\n";
else cout << "No\n";
}
int main(){
freopen("delete.in", "r", stdin);
freopen("delete.out", "w", stdout);
T = read();
while (T--) solve();
return 0;
}
T3
将题目意思转化一下,就是求子序列和为 \(0\) 所在区间的个数,直接背包然后拆分贡献计算。
#include<iostream>
#define int long long
using namespace std;
inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
const int N = 1e3 + 10, M = 2e5 + 10, K = 1e5, mod = 998244353;
int n, ans;
int a[N], dp[M];
signed main(){
freopen("seq.in", "r", stdin);
freopen("seq.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 2; i <= n - 1; i++){
if (a[i] >= 0){
for (int j = K; j >= -K; j--)
if (j - a[i] >= -K && j - a[i] <= K)
dp[j + K] = (dp[j + K] + dp[j + K - a[i]]) % mod;
}else{
for (int j = -K; j <= K; j++)
if (j - a[i] >= -K && j - a[i] <= K)
dp[j + K] = (dp[j + K] + dp[j + K - a[i]]) % mod;
}
dp[a[i] + K] = (dp[a[i] + K] + i - 1) % mod;
ans = (ans + dp[K]) % mod;
}
cout << (ans + n * (n + 1) / 2 % mod) % mod;
return 0;
}
T4
不会。
标签:20241030noip,register,共同体,int,while,read,OIFC,include,getchar From: https://www.cnblogs.com/bryceyyds/p/18521303