2020 NOIP 补题

P7113 [NOIP2020] 排水系统

拓扑排序，但是 \(\_\_int128\)。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int __int128
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

void write ( int x )
{
    if ( x < 0 ) cout.put('-') , x = -x;
    if ( x > 9 ) write ( x / 10 );
    cout.put ( x % 10 + '0' );
}

void writel ( int x ) { write(x) , cout.put(endl); }
void writei ( int x ) { write(x) , cout.put(' '); }

int n , m , in[N] , d[N];
pii f[N];

vector<int> e[N];
inl void add ( int u , int v ) { e[u].eb(v); }

queue<int> q;

int lcm ( int a , int b ) { return a / __gcd ( a , b ) * b; }

pii solve ( pii x , pii y )
{
    if ( y.se == 0 ) return x;
    if ( x.se == 0 ) return y;
    pii res = { 0 , 0 };
    res.se = lcm ( x.se , y.se );
    res.fi = x.fi * ( res.se / x.se ) + y.fi * ( res.se / y.se );
    return res;
}

void out ( pii x )
{
    int gg = __gcd ( x.fi , x.se );
    x.fi /= gg , x.se /= gg;
    writei ( x.fi ) , writel ( x.se );
}

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read() , m = read();
    for ( int i = 1 ; i <= n ; i ++ )
    {
        d[i] = read();
        for ( int j = 1 , v ; j <= d[i] ; j ++ ) v = read() , add ( i , v ) , in[v] ++;
    }
    for ( int i = 1 ; i <= m ; i ++ ) f[i] = { 1 , 1 };
    for ( int i = 1 ; i <= n ; i ++ ) if ( !in[i] ) q.push(i);
    while ( !q.empty() )
    {
        int u = q.front(); q.pop();
        for ( auto v : e[u] )
        {
            f[v] = solve ( f[v] , mkp ( f[u].fi , f[u].se * e[u].size() ) );
            if ( -- in[v] == 0 ) q.push(v);
        }
    }
    for ( int i = 1 ; i <= n ; i ++ ) if ( !d[i] ) out ( f[i] );
    return 0;
}

P7114 [NOIP2020] 字符串匹配

分两档部分分实现：

\(48pts\) 这一部分实际上是要用 \(O(n^2)\) 的算法解决的，但是我们的 \(O(n^3)\) 实现良好的话是可以解决的。

考虑枚举每一个 \(AB\) 的末尾节点 \(i\)，向后暴力匹配 \((AB)^j\) 中的 \(j\)，每次能匹配上之后，我们后面的一段自然是 \(C\) 串，那么我们暴力枚举 \(AB\) 之间的分界点，对所有合法的前缀 \(tot\le\) 后缀 \(tot\) 的串进行统计。

严重跑不满，过编即 \(48pts\)。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

void write ( int x )
{
    if ( x < 0 ) cout.put('-') , x = -x;
    if ( x > 9 ) write ( x / 10 );
    cout.put ( x % 10 + '0' );
}

void writel ( int x ) { write(x) , cout.put(endl); }
void writei ( int x ) { write(x) , cout.put(' '); }

int n , vis[27] , ans , tot;

string s;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int T = read();
    while ( T -- )
    {
        ans = 0;
        cin >> s , n = s.size() , s = " " + s;
        for ( int i = 2 ; i < n ; i ++ )//AB的末尾。
        {
            int cnt = 1;
            while ( cnt * i < n )
            {
                int flag = 1;
                for ( int st = 1 , j = cnt * i - i + 1 ; st <= i && j <= cnt * i ; j ++ , st ++ )
                    if ( s[st] != s[j] ) flag = 0;
                if ( flag )
                {
                    memset ( vis , 0 , sizeof vis ) , tot = 0;
                    for ( int k = cnt * i + 1 ; k <= n ; k ++ )
                    {
                        if ( ++ vis[s[k]-'a'] % 2 == 1 ) ++ tot;
                        else -- tot;
                    }
                    int lim = tot;
                    memset ( vis , 0 , sizeof vis ) , tot = 0;
                    for ( int k = 1 ; k < i ; k ++ )//a的ed
                    {
                        if ( ++ vis[s[k]-'a'] % 2 == 1 ) ++ tot;
                        else -- tot;
                        if ( tot <= lim ) ++ ans;
                    }
                }
                else break;
                ++ cnt;
            }
        }
        cout << ans << endl;
    }

    return 0;
}

将暴力匹配转化为哈希值匹配，可以降低复杂度到调和级数。

开一个 \(suf_i\) 数组表示后缀的出现奇数次字符的数量 \(tot\) ，由于这个数量最多可以到 \(26\) 那么我们对于每一个枚举的 \(i\)，开一个桶 \(sum_j\) 表示 \([1,i-1]\) 中有多少个 \(tot\le j\) 的前缀，那么我们可以做到 \(O(1)\) 统计。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int N = ( 1 << 20 ) + 5;
const int mod = 1e9 + 7;
const int base = 131;
const int inf = 0x3f3f3f3f;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

void write ( int x )
{
    if ( x < 0 ) cout.put('-') , x = -x;
    if ( x > 9 ) write ( x / 10 );
    cout.put ( x % 10 + '0' );
}

void writel ( int x ) { write(x) , cout.put(endl); }
void writei ( int x ) { write(x) , cout.put(' '); }

int n , hashh[N] , cf[N] , vis[base] , ans , tot , suf[N] , sum[N] , bel[N];

string s;

int check ( int l , int r , int L , int R )
{
    int val1 = ( hashh[r] - hashh[l-1] * cf[r-l+1] % mod + mod ) % mod;
    int val2 = ( hashh[R] - hashh[L-1] * cf[R-L+1] % mod + mod ) % mod;
    return val1 == val2;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    int T = read();
    while ( T -- )
    {
        memset ( suf , 0 , sizeof suf );
        memset ( sum , 0 , sizeof sum );
        ans = 0;
        cin >> s , n = s.size() , s = " " + s;
        for ( int i = 1 ; i <= n ; i ++ ) hashh[i] = ( hashh[i-1] * base % mod + s[i] ) % mod;
        cf[0] = 1; for ( int i = 1 ; i <= n ; i ++ ) cf[i] = cf[i-1] * base % mod;
        memset ( vis , 0 , sizeof vis ) , tot = 0;
        for ( int i = n ; i ; i -- )
        {
            if ( ++ vis[s[i]-'a'] % 2 == 1 ) ++ tot;
            else -- tot;
            suf[i] = tot;
        }
        memset ( vis , 0 , sizeof vis ) , tot = 0;
        for ( int i = 2 ; i < n ; i ++ )//AB的末尾。
        {
            if ( ++ vis[s[i-1]-'a'] % 2 == 1 ) ++ tot;
            else -- tot;
            for ( int j = tot ; j <= 26 ; j ++ ) ++ sum[j];
            int cnt = 1;
            while ( cnt * i < n )
            {
                if ( check ( 1 , i , ( cnt - 1 ) * i + 1 , cnt * i ) ) ans += sum[suf[cnt*i+1]];
                else break;
                ++ cnt;
            }
        }
        cout << ans << endl;
    }

    return 0;
}

P7115 [NOIP2020] 移球游戏

\(2\) 个柱子的时候方法很多，这里采用题解中的部分分方法。

\(10pts\)：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int N = 2e3 + 5;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , m , a[N][N] , cnt;

stack<int> sta[4];//2上放0，3上放1
vector<pii> vec;

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read() , m = read();
    for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++ ) a[i][j] = read() , sta[i].push(a[i][j]);
    for ( int i = 1 ; i <= m ; i ++ ) cnt += ( a[1][i] == 1 );
    for ( int i = 1 ; i <= cnt ; i ++ ) sta[3].push(sta[2].top()) , sta[2].pop() , vec.eb(2,3);
    for ( int i = 1 ; i <= m ; i ++ )
    {
        if ( sta[1].top() == 1 ) sta[2].push(sta[1].top()) , sta[1].pop() , vec.eb(1,2);
        else sta[3].push(sta[1].top()) , sta[1].pop() , vec.eb(1,3);
    }
    for ( int i = 1 ; i <= cnt ; i ++ ) sta[1].push(sta[2].top()) , sta[2].pop() , vec.eb(2,1); 
    for ( int i = 1 ; i <= m - cnt ; i ++ ) sta[1].push(sta[3].top()) , sta[3].pop() , vec.eb(3,1);
    for ( int i = 1 ; i <= m - cnt ; i ++ ) sta[3].push(sta[2].top()) , sta[2].pop() , vec.eb(2,3);
    for ( int i = 1 ; i <= m - cnt ; i ++ ) sta[2].push(sta[1].top()) , sta[1].pop() , vec.eb(1,2);
    for ( int i = 1 ; i <= m ; i ++ )
    {
        if ( sta[3].top() == 1 ) sta[1].push(sta[3].top()) , sta[3].pop() , vec.eb(3,1);
        else sta[2].push(sta[3].top()) , sta[3].pop() , vec.eb(3,2);
    }
    cout << vec.size() << endl;
    for ( auto v : vec ) cout << v.fi << ' ' << v.se << endl;
    return 0;
}

P7116 [NOIP2020] 微信步数

考虑转化条件：将每个点走的步数变成每一轮之后还剩下多少节点。

那么对于每一个维度，维护一个偏移量 \(delta\)，再维护左面和右面最多出去的数量 \(l_i,r_i\)。

那么每一轮的贡献就是 \(\prod_{i=1}^k w_i-(r_i-l_i)\)，当有一个维度的 \(w_i-(r_i-l_i)\le 0\) 时输出答案。

无解当且仅当有一轮之后所有维度的 \(del\) 都为 \(0\)。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define pb pop_back
#define mid (l+r>>1)
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define getchar() cin.get()
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define int long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int read()
{
	int f = 1 , x = 0;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , k , w[N] , ans = 1 , del[N] , l[N] , r[N] , c[N] , d[N];

signed main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    n = read() , k = read();
    for ( int i = 1 ; i <= k ; i ++ ) w[i] = read() , ( ans *= w[i] ) %= mod;
    for ( int i = 1 ; i <= n ; i ++ ) c[i] = read() , d[i] = read();
    while (1)
    {
        for ( int i = 1 ; i <= n ; i ++ )
        {
            del[c[i]] += d[i];
            l[c[i]] = min ( del[c[i]] , l[c[i]] );
            r[c[i]] = max ( del[c[i]] , r[c[i]] );
            int res = 1;
            for ( int j = 1 ; j <= k ; j ++ ) 
            {
                if ( r[j] + ( -l[j] ) >= w[j] ) cout << ans << endl , exit(0);
                ( res *= ( w[j] - ( r[j] + ( -l[j] ) ) ) ) %= mod;
            }
            ( ans += res ) %= mod;
        }   
        int flag = 1;
        for ( int i = 1 ; i <= k ; i ++ ) if ( del[i] ) flag = 0;
        if ( flag ) cout << -1 << endl , exit(0);
    }
    return 0;
}

本栏目推荐文章
• P9871 [NOIP2023] 天天爱打卡
• mrctf2020_easyoverflow
• CVE-2020-11800
• 【LeetCode 1635. Hopper 公司查询 I】with recursive生成2020年每月的最后一天
• 2020-2021 ACM-ICPC, Asia Seoul Regional Contest
• [ACTF2020 新生赛]Exec 1
• wustctf2020_getshell_2
• NOIP2023vp
• NOIP2023 游记
• P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G(memset用法)

2020 NOIP2020 noip noip 2020 游记noip 2020 2020 2021 2022 noip 报告noip 2020 p7116 2020 noip 2020 2020.11 2020.03 2020.2