2023杭电多校02

2023-07-22
作者 Kyooma
~12.86K 字

题目来自: 2023“钉耙编程”中国大学生算法设计超级联赛（2）

Solved	Rank	A	B	C	D	E	F	G	H	I	J	K	L	M
6 / 13	168 / 1200	O	O	-	O	-	-	O	-	O	-	O	Ø	-

Ø 赛后通过
O 在比赛中通过
! 尝试了但是失败了
- 没有尝试

A - Alice Game

SOLUTION

打表结论题

CODE

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
const int N=1e3+10;
void solve(){
    int x,n,i,k,j;
    read(k);
    read(n);
    if(!n){
        cout<<"Bob\n";
        return;
    }
    if(n<=k){
        cout<<"Alice\n";
        return;
    }
    n=n-k-1;
    x=k*4+2;
    if(n%x==0) cout<<"Bob\n";
    else cout<<"Alice\n";
}

int main(){
    int T = 1;
    read(T);
    while(T--){
        solve();
    }
    return 0;
}

B - Binary Number

SOLUTION

分类讨论的签到题

CODE

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void solve(){
    int n;
    ll k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0, ok = 0;
    for(int i = 0; i < n && k > 0; i++){
        if(s[i] != '0') continue;
        int j = i;
        while(j < n && s[j] == s[i]) j++;j--;
        k--;
        ok = 1;
        for(int p = i; p <= j; p++) s[p] = '1';
        i = j;
    }
    if(!k){
        cout << s << '\n';
        return;
    }
    //
    if(n == 1){
        if(k & 1){
            cout << "0\n";
        }else{
            cout << "1\n";
        }
    }else{
        if(ok || k > 1){
            cout << s << '\n';
            return;
        }
        // k = 1
        s[n - 1] = '0';
        cout << s << '\n';
    }
}

int main(){
    int T = 1;
    // read(T);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

D - Card Game

SOLUTION

推柿子（打表）签到题

CODE

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

ll qpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve(){
    int n;
    read(n);
    ll ans = qpow(2, n - 1) - 1;
    if(ans < 0) ans += mod;
    cout << ans << '\n';
}

int main(){
    int T = 1;
    read(T);
    while(T--){
        solve();
    }
    return 0;
}

G - foreverlasting and fried-chicken

SOLUTION

枚举度最大的两个点，再求出与这两个点同时有边的点个数，可以使用bitset。

CODE

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
const int N=1e3+10;
const int p=1e9+7;
bitset<1010>a[N];
int d[N];
int C[N][N];
void init(){
    int i,j,n=1e3;
    C[0][0]=1;
    for(i=1;i<=n;i++){
        C[i][0]=1;
        for(j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
}
void solve(){
    int n,m,i,x,y,j,k,ans=0;
    read(n);
    read(m);
    for(i=1;i<=n;i++) a[i].set();
    for(i=1;i<=n;i++) d[i]=0;
    for(i=1;i<=m;i++){
        read(x);
        read(y);
        d[x]++;
        d[y]++;
        a[x][y]=a[y][x]=0;
    }
    for(i=1;i<=n;i++){
        if(d[i]<4) continue;
        for(j=i+1;j<=n;j++){
            if(d[j]<4) continue;
            x=0;
            bitset<1010>sta=(a[i]|a[j]);
            x=1010-sta.count();
            // cout<<x<<'\n';
            int ok = 0;
            if(!a[i][j]) ok = 1;
            if(x>=4){
                if(d[i] - ok>=6) ans=(ans+1ll*C[x][4]*C[d[i] - ok-4][2])%p;
                if(d[j]-ok>=6) ans=(ans+1ll*C[x][4]*C[d[j]-ok-4][2])%p;
            }
        }
    }
    cout<<ans<<'\n';
}

int main(){
    int T = 1;
    read(T);
    init();
    while(T--){
        solve();
    }
    return 0;
}

I - String Problem

SOLUTION

签到题

CODE

#include<bits/stdc++.h>

using namespace std;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}

void solve(){
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < s.size(); i++){
        int j = i;
        while(j < s.size() && s[j] == s[i]) j++;j--;
        ans += j - i;
        i = j;
    }
    cout << ans << '\n';
}

int main(){
    int T = 1;
    // read(T);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

K - SPY finding NPY

SOLUTION

推柿子，之后可以在 $O(n^2)$ 内预处理所有答案

CODE

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 998244353;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(long long &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
void read(int &n){
	for(n=0;(c=gc())<'0'||c>'9';);
	for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
}
const int N=1e4+10;
const int p=1e9+7;

int b[N];
void init(int n){
    int i,ans=0,p;
    long double mx=0,sum=0,y,d=1./n,eps=1e-12;
    p=0;
    mx=1./n;
    for(i=1;i<n;i++){
        sum+=1./(n-i);
    }
    for(i=1;i<n;i++){
        y=d*sum*i;
        if(fabs(y-mx)>eps){
            if(y>mx){
                p=i;
                mx=y;
            }
        }
        sum-=1./i;
    }
    b[n]=p;
}
void solve(){
    int n,i,x,y,ans=0,p;
    double mx=0;
    read(n);
    cout<<b[n]<<'\n';
}

int main(){
    int T = 1;
    for(int i=1;i<=1e4;i++) init(i);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    read(T);
    while(T--){
        solve();
    }
    return 0;
}

L - Coin

SOLUTION

最大流，源点连向每个点的流量为1，每一轮需要拆出一个新点，与之前的旧点（若有）连边的流量为 $a_i$，并与这轮中另一个点建一条正流量为1逆流量也为1点边，最后 $k$ 个点连向汇点，流量为 $a_i$，之后跑dinic即可。

undefined

ps. 赛中觉得3000个点 3000条边的最大流不太可行就否了。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f, N = 20000, M = 1e7 + 10;
struct edge {
    int to, next;
    ll w;//w为流量
} e[M];
int head[N], idx, cur[N];
int dist[N], s, t, tn;
bool vis[N];

void init() {
    idx = 0;
    for(int i = 1; i <= tn; i++) head[i] = -1;
}

void _add(int a, int b, ll c) {
    e[idx] = {b, head[a], c};
    head[a] = idx++;
}

void add(int a, int b, ll c, ll re = 0){
    _add(a, b, c);
    _add(b, a, re);
}

bool bfs() {
    for (int i = 1; i <= tn; i++) vis[i] = false;
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dist[s] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i != -1; i = e[i].next) {
            int to = e[i].to;
            ll w = e[i].w;
            if (!vis[to] && w) {
                vis[to] = true;
                dist[to] = dist[x] + 1;
                q.push(to);
            }
        }
    }
    return vis[t];
}

ll dfs(int x, ll flow) {
    if (x == t || !flow) return flow;
    ll delta = 0, f;
    for (int i = cur[x]; i != -1; i = e[i].next) {
        int to = e[i].to;
        ll w = e[i].w;
        cur[x] = i;
        if (dist[to] == dist[x] + 1 && (f = dfs(to, min(flow, w))) > 0) {
            e[i].w -= f;
            e[i ^ 1].w += f;
            flow -= f;
            delta += f;
            if (flow == 0) break;
        }
    }
    return delta;
}

ll MaxFlow() {
    ll ans = 0;
    while (bfs()) {
        for (int i = 1; i <= tn; i++) cur[i] = head[i];
        ans += dfs(s, inf);
    }
    return ans;
}

int a[N], prv[N];

void solve() {
    int n, m, k, tot = 0;
    cin >> n >> m >> k;
    s = 2 * m + 1;
    t = tn = s + 1;
    init();
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        prv[i] = s;
    }
    for(int i = 0, u, v; i < m; i++){
        cin >> u >> v;
        if(prv[u] == s) add(prv[u], tot + 1, 1);
        else add(prv[u], tot + 1, a[u]);
        prv[u] = ++tot;
        if(prv[v] == s) add(prv[v], tot + 1, 1);
        else add(prv[v], tot + 1, a[v]);
        prv[v] = ++tot;
        add(prv[u], prv[v], 1, 1);
    }
    for(int i = 0, x; i < k; i++){
        cin >> x;
        add(prv[x], t, a[x]);
    }
    cout << MaxFlow() << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) solve();
    return 0;
}

Kyooma's Blog

2023杭电多校02

A - Alice Game

B - Binary Number

D - Card Game

G - foreverlasting and fried-chicken

I - String Problem

K - SPY finding NPY

L - Coin

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

Kyooma's Blog

A - Alice Game

B - Binary Number

D - Card Game

G - foreverlasting and fried-chicken

I - String Problem

K - SPY finding NPY

L - Coin

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可