189 8069 5689

2022SDNU-ACM结训赛题解-创新互联

首先感谢一下各位出题人的精心准备、验题人的辛勤付出、以及选手的积极参加

创新互联专注骨干网络服务器租用10年,服务更有保障!服务器租用,四川服务器托管 成都服务器租用,成都服务器托管,骨干网络带宽,享受低延迟,高速访问。灵活、实现低成本的共享或公网数据中心高速带宽的专属高性能服务器。题解 Problem A 柳予欣的归来【数学】

出题人: bhq

没想到一血是被打完山大的牛客比赛后来结训赛玩的wyx拿走的!

题目描述:

计算 ( ∑ 0 < d < p d − 1 ) m (\sum_{0

思路:

本题是一个小思维题,对于一个素数 p p p 来说, p p p 的剩余系的每个元素的逆仍然构成它的剩余系。我们记 p p p 的剩余系是 P P P ,对于 a ∈ P a \in P a∈P 来说, a a a 的逆一共有两种情况,第一种情况是 a − 1 = a a^{-1}=a a−1=a,第二种情况是 a − 1 = b , b ∈ P a^{-1}=b,b\in P a−1=b,b∈P,此时 b − 1 = a b^{-1}=a b−1=a,所以总体来说取逆并不会有什么变化,括号里面本质上就是一个等差数列求和。注意数据范围, p p p 会很大,所以 p ∗ ( p − 1 ) p*(p-1) p∗(p−1) 时会爆 l o n g l o n g longlong longlong,所以要先取模 998244353 998244353 998244353,除以 2 2 2 转化成乘 2 2 2 的逆元,之后做一遍快速幂就可以了。

#include#include#include#include#include#include#include#include
#include#includeusing namespace std;
#define ll long long
const ll N = 1e5+5;
const ll mod = 998244353;

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

int main()
{std::ios::sync_with_stdio(false);
    ll p, m;
    cin >>p >>m;
    p %= mod;
    ll ans = (p * (p-1) % mod) * qpow(2, mod-2) % mod;
    cout<< qpow(ans, m)<< '\n';
	return 0;
}
Problem B 收收心找个电子厂上班了【区间贪心/差分约束】

出题人: LYJ

很可惜,赛时并没有人过这个题

题目描述:

给你m种条件(l[i],r[i],c[i]),要求构造一个01串,使得l[i]r[i]中至少有c[i]个1,问满足所有条件下1的数量最少的串是什么

思路1

经典的区间贪心问题,我们将m种条件按照r从大到小排序

对于一个区间[l,r],我们先计算一下区间中已经存在了多少个1,剩下的1就选最靠近r的那几个不是1的位置。

所以我们需要一个数据结构维护一下区间查询/更新 1的数量,还需要一个数据结构可以知道当前这个位置往前的一个不是1的位置,来进行更新

我们可以用树状数组或者线段树进行区间的维护

利用并查集进行维护i往前的第一个不为1的位置

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define lowbit(x) (x&(-x))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x, y, p;
struct ran{int l, r, x;
    int id;
    bool operator< (const ran &a)const{return r< a.r;
    }
}tr[MAX];

int ans[MAX];
int fa[MAX];
int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}

int ar[MAX];
void add(int id){while(id<= n){++ar[id];
        id += lowbit(id);
    }
}
int getans(int id){int ans = 0;
    while(id){ans += ar[id];
        id -= lowbit(id);
    }
    return ans;
}

void work(){cin >>n >>m;
    for(int i = 1; i<= m; ++i){cin >>tr[i].l >>tr[i].r >>tr[i].x;
        tr[i].id = i;
    }
    sort(tr+1, tr+1+m);
    for(int i = 1; i<= n; ++i)fa[i] = i;
    for(int i = 1; i<= m; ++i){tr[i].x -= (getans(tr[i].r) - getans(tr[i].l - 1));
        if(tr[i].x<= 0)continue;
        for(int id = getfa(tr[i].r); tr[i].x;id = getfa(id)){add(id);
            --tr[i].x;
            fa[id] = getfa(id-1);
            ans[id] = 1;
        }
    }
    for(int i = 1; i<= n; ++i)cout<< ans[i]<< " \n"[i==n];
}


int main(){io;
    work();
    return 0;
}
思路2:

差分约束板子题

假设所求数组叫做ar[i]

则我们令sum[i]表示ar数组的前缀和数组,对于l, r, c我们可以转换成sum[r]-sum[l-1] >= c,因为求的是最小值,所以跑最长路,用>号,也就是sum[r] >= sum[l-1] + c,建一条l-1r的权值为c的边,但是为了避免使用0,我们改成lr+1建一条边

因为是前缀和,且一个位置最多一个1,所以建立一个0≤sum[i]-sum[i-1]≤1的条件,拆开来看就是sum[i]≥sum[i-1]+0,建一条从i-1i的权值为0的边,sum[i-1]≥sum[i]-1,建立一条从ii-1的权值为-1的边,因为存在负权边,所以跑SPFA

得到的前缀和数组再做一次差分就可以得到原数组

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define No cout<<"No\n"
#define Yes cout<<"Yes\n"
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pairpii;

#define MAX 1000000 + 50
int n, m, k, l, r, c, p;

int tot;
int head[MAX];
struct ran{int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void spfa(){dequeq;
    for(int i = 1; i<= n; ++i){q.push_back(i);
        dis[i] = 0;
        vis[i] = 1;
    }
    while (!q.empty()) {int u = q.front();q.pop_front();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){int v = tr[i].to;
            if(dis[v]< dis[u] + tr[i].val){dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){vis[v] = 1;
                    if(!q.empty() && dis[q.front()] >dis[v])q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    for(int i = 2; i<= n + 1; ++i){cout<< dis[i] - dis[i - 1]<< " \n"[i==n+1];
    }
}


void work(){cin >>n >>m;
    for(int i = 1; i<= n; ++i){add(i, i+1, 0);
        add(i+1, i, -1);
    }
    for(int i = 1; i<= m; ++i){cin >>l >>r >>c;
        add(l, r+1, c);
    }
    spfa();
}


int main(){io;
    work();
    return 0;
}
Problem C 我没有脑子【打表/矩阵快速幂】

出题人: JBQ

很遗憾这么签到的一道题没有人做

题目描述:

生兔子,兔子的数量是斐波那契数列

问第l亿年到第r亿年出生了多少兔子,且出生的兔子并不包括第l年出生的兔子,第0年是没有兔子出生的

思路:

观察一下数据范围,会发现0<=l,r<=300,显然是个简单的打表题,我们可以暴力跑斐波那契求出0亿到300亿的斐波那契数,跑的时候可以用三个变量来回倒换即可避免数组开不下的问题,大概本地跑个几分钟就能打出表,然后用数组记录下来第i亿年的斐波那契数,这就是一个前缀和,查询哪个区间就利用前缀和的性质计算一下就行

因为涉及到减法,所以会出现负数的情况,记得+mod后再对mod取模

当然,这是一个矩阵快速幂的板子题,套了就能过

#includeusing namespace std;
typedef long long ll;
const double pi = acos(-1);
const ll mod = 998244353;

ll qz[] = {0,798940737,702476549,882271746,158813243,717203476,338005251,116925432,142361015,915249973,857532739,753217439,520526462,729616988,647870145,371082495,841434648,373792903,192185450,309635100,846033167,574139965,802208229,788931688,653823084,498623881,381227773,444199493,541776490,385469308,204954591,661354559,261075692,24044029,83866001,584279557,45051147,173356045,821097718,163787363,787428576,988607439,538194736,477301409,856030254,182481274,696848072,333236726,460460936,413870920,87699598,677867260,933901576,122519290,433328905,517328471,66133697,748952995,271526780,951814203,603251788,538205993,786735739,210759723,471369471,844152090,451425750,64320864,664523635,755126352,322282207,848963789,601663281,955920251,188264055,448820184,924870015,870684039,690825122,363991368,510949049,787514543,868353515,23576757,729097988,456367806,120642843,745912349,311624691,396321784,468768789,940449311,479622530,706285186,96018834,614222128,531387322,51266835,824627665,26443258,661596038,328505115,470346561,301752734,536314862,51032382,156416715,858226445,377889809,802029259,44891519,618514642,28412917,845529642,248409413,138438148,983915659,347993720,721251618,402015592,208058847,859078897,523989448,504052355,248065071,501719314,706051327,634108576,257642722,164709287,863618638,306954392,910875941,655103461,467141818,572508067,664175525,947444075,469933222,883991102,757741015,1474536,709356522,802778892,578012184,112096396,37994672,704609404,18735451,258157019,554151314,327440787,420681318,119115175,114348722,45849809,854152074,660727321,437865313,839664896,833951917,574989040,378592331,262142690,699881570,924047133,283460224,695823769,961649873,956270153,66045054,288527356,116809227,330703987,815531292,536702953,963616030,172058590,361328034,404667451,335937034,608229080,406337321,288852773,916154288,405321356,248562231,772003667,344018140,279265806,721778550,617440080,379179999,472866396,426600720,144286727,723894575,399751987,354317264,540289590,440230859,846662817,864857587,718655634,950096265,290426201,791678815,231978197,160685153,385229934,71853234,451895282,34336651,939727748,451455552,731675730,291527149,485355441,340321224,978564745,683403470,256607555,459702481,754509303,983134135,547374590,123507260,123212517,907699376,880893030,380044243,404686542,919434049,296606692,738071182,474476191,947772155,54578357,312799315,66989458,797607101,925860402,205607764,532696276,90867276,936962661,877887130,864602607,245414428,760338293,213637659,193249572,807595867,285884919,259032359,770485780,361717598,182833844,813779029,873553462,356707666,208580125,718898155,707280088,309609449,162174566,648557431,919420983,940109378,631849990,799994020,679817491,929829530,453450192,264396037,431709960,795394812,17661181,677218455,695586920,475003070,543790903,220685197,455960728,932178450,803872141,700865964,215343465,176830374,118069191,353690631,564849453,512987043,169310973,857323540,761677403,906282770,943136960,292380651,93349738,29943185};

int main()
{ll T,p,q;
	cin>>T;
	while(T--){cin>>p>>q;
		cout<<(qz[q] - qz[p] + mod)%mod<
#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 998244353
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x, y;
int tr[MAX];

struct Matrix{ll tr[2][2];
    Matrix(){mem(tr, 0);
    }
    Matrix operator * (const Matrix y){Matrix ans;
        for(int i = 0; i< 2; ++i){for(int j = 0; j< 2; ++j){for(int k = 0; k< 2; ++k){(ans.tr[i][j] += tr[i][k] * y.tr[k][j]) %= mod7;
                }
            }
        }
        return ans;
    }
    void operator = (const Matrix b){for(int i = 0; i< 2; ++i){for(int j = 0; j< 2; ++j){tr[i][j] = b.tr[i][j];
            }
        }
    }
};
ll getans(ll n){Matrix ans, cnt;
    ans.tr[0][0] = ans.tr[1][1] = 1;
    cnt.tr[0][0] = cnt.tr[0][1] = cnt.tr[1][0] = 1;
    while(n){if(n & 1)ans = ans * cnt;
        cnt = cnt * cnt;
        n /= 2;
    }
    return ans.tr[0][0];
}

ll fuck[MAX];

void work(){for(ll i = 1; i<= 300; ++i){fuck[i] = getans(i * 100000000ll - 1);
    }
    int t;cin>>t;
    while(t--){cin >>x >>y;
        cout<< (fuck[y] - fuck[x] + mod7) % mod7<< endl;
    }
}


int main(){io;
    work();
    return 0;
}
Problem D 我是杀猪饲料,祝你天天开心【签到】

出题人: LYJ

本来没想出hello world的题,但是突然接到通知大二不打了,这套题只给大一打,我就连夜加了一道

如果没有这个题,大家很可能五个小时都在牢底坐穿

还是要祝一下蛇姐生日快乐耶!

题目描述:

输出”蛇姐生日快乐!!!”即可

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){cout<< "蛇姐生日快乐!!!";
}

int main(){io;
    work();
    return 0;
}
Problem E 没什么特殊意义,就是想混一个最长的题目名字,然后让大家点进来做这道题

出题人: NXY

关于xygg出了个权值线段树却被两个人用别的思路随便卡过去这件事

思路:

第一种做法:离散化 + 权值线段树
我们发现每个数本身没有什么用,我们需要的仅仅是他们之间的大小关系,而 N N N 又不是很大,所以考虑离散化。
然后把离散化之后的序列用权值线段树维护起来。

第二种做法:平衡树
动态查询第 k k k 大数,容易想到平衡树直接维护

第三种做法:对顶堆
szz \texttt{szz} szz 的考场做法。

第四种做法: 主席树
gts \texttt{gts} gts 的考场做法

大家如果要补题的话建议学习第一种做法和第三种做法,第一种做法很典型很常见,是一种必不可少的技能点。第三种做法思维上很巧妙很有意思,并且代码简短容易理解,也同样建议大家学习

#includeusing namespace std;
const int N = 1e5 + 10;

int n,w;
int a[N],b[N],c[N];

bool cmp(int x , int y)
{return x >y;}

struct NO
{int l;
    int r;
    int w;
};

struct SigmentT
{NO t[N * 4];
    void Build(int p , int l , int r)
    {t[p].l = l; t[p].r = r;
        if(l == r) return;
        int mid = (l + r) >>1;
        Build(p<< 1 , l , mid);
        Build(p<< 1 | 1 , mid + 1 , r);
    }

    void Updata(int p , int w)
    {if(t[p].l == t[p].r) {t[p].w++; return;
        }
        int mid = (t[p].l + t[p].r) >>1;
        if(w<= mid) Updata(p<< 1 , w);
        else Updata(p<< 1 | 1 , w);
        t[p].w = t[p<< 1].w + t[p<< 1 | 1].w;
    }

    int Query(int p , int k)
    {if(t[p].l == t[p].r) return t[p].l;
        if(t[p<< 1].w< k) return Query(p<< 1 | 1, k - t[p<< 1].w);
        else return Query(p<< 1 , k);
    }
}tr;

int main()
{//freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&w); 
    for(int i = 1; i<= n; i++)
        scanf("%d",&a[i]) , b[i] = a[i];

    std::sort(b + 1 , b + 1 + n);
    int LEN = std::unique(b + 1 , b + 1 + n) - b - 1;
    for(int i = 1, tmp; i<= n; i++)
        tmp = a[i] , a[i] = std::lower_bound(b + 1 , b + 1 + LEN , a[i]) - b , c[a[i]] = tmp;
    
    tr.Build(1 , 0 , LEN);
    for(int i = 1; i<= n; i++)
    {int m = max(1 , i * w / 100);
        tr.Updata(1 , a[i]);
        printf("%d ",c[tr.Query(1 , i - m + 1)]);
    }
    
}
#includeconst int N = 3e5 + 10;

int n,w;
int a[N];

struct No {int p,siz,val,sel,son[2];
};

struct SBT{int rt,idx;
    No t[N];

    void Pushup(int u) {t[u].siz = t[t[u].son[0]].siz + t[t[u].son[1]].siz + t[u].sel;
    }

    void rotate(int u) {int y = t[u].p , z = t[y].p;
        int k = t[y].son[1] == u;
        t[z].son[t[z].son[1] == y] = u , t[u].p = z;
        t[y].son[k] = t[u].son[k ^ 1] , t[t[u].son[k ^ 1]].p = y;
        t[u].son[k ^ 1] = y , t[y].p = u;
        Pushup(y) , Pushup(u);
    }

    void Splay(int u , int p) {while(t[u].p != p) {int y = t[u].p , z = t[y].p;
            if(z != p)
                if((t[z].son[1] == y) ^ (t[y].son[1] == u))
                    rotate(u);
                else rotate(y);
            rotate(u);
        }
        if(!p) rt = u;
    }

    void insert(int val) {int u = rt , p = 0;
        while(u) {if(val == t[u].val) break;
            p = u , u = t[u].son[val >t[u].val];
        }
        if(!u) u = ++idx;
        t[u].sel++;t[u].p = p;t[u].val = val;
        if(p) t[p].son[val >t[p].val] = u;
        Splay(u , 0);
    }

    int getk(int k) {int u = rt;
        while(1) {if(k<= t[t[u].son[0]].siz) u = t[u].son[0];
            else if(k<= t[t[u].son[0]].siz + t[u].sel) {Splay(u , 0); return t[u].val;
            }
            else k -= t[t[u].son[0]].siz + t[u].sel , u = t[u].son[1];
        }
    }
}tr;

const int inf = 1e9;

int main() {//freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&w); tr.insert(-1) , tr.insert(inf);
    for(int i = 1 , x; i<= n; i++) {scanf("%d",&x); tr.insert(x);
        int end = std::max(1 , i * w / 100);
        printf("%d ",tr.getk(i - end + 1 + 1));
    }
}
Problem F 泷1千0(hard version)【构造】

出题人: DJK

看hard版之前先看看easy版的

题目描述:

跟简单版相比,不同点在于字符串长度,和操作总次数发生了变化。

思路:

给出其中一种构造方式。

由于是对前缀进行操作,容易想到从后向前匹配两个01串,当 s 串 与 t 串 s串与t串 s串与t串在位置 i i i不同时,执行操作 i i i,但当执行完操作 i i i后, s 串 和 t 串 s串和t串 s串和t串在位置 i i i依旧可能不匹配,所以我们需要预处理 s s s串,让它全变成 0 0 0或 1 1 1,这样的话就可以保证执行操作 i i i后,一定匹配。

容易发现,至多操作 2 ∗ n 2*n 2∗n次(预处理至多 n n n次,从后向前匹配过程至多 n n n次)。

#includeusing namespace std;
typedef long long ll;
//#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define pii pairconst int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-4;
int n, sum;
string s1, s2;
char ch;
int ans[maxn];

int main()
{io;
    //freopen("20.in", "r", stdin);
    //freopen("20.out", "w", stdout);
    cin >>s1 >>s2;
    n = s1.size();
    s1 = '$' + s1;
    s2 = '$' + s2;
    sum = 0;
    for(int i = 2; i<= n; ++i)
    {if(s1[i] != s1[i - 1])
            ans[++sum] = i - 1;
    }
    ch = s1[n] - '0';
    for(int i = n; i >0; --i)
    {if(ch != (s2[i] - '0'))
        {ans[++sum] = i;
            ch = 1 - ch;
        }
    }
    cout<< sum;
    for(int i = 1; i<= sum; ++i) cout<< ' '<< ans[i];
    cout<< '\n';
    return 0;
}
Problem G A+B Problem【ull自然溢出】

出题人:NXY

a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊

这个题最开始的时候是NXY想考ull自然溢出等于对264取模,所以题目名称本来叫做**“自然溢出啥事没有!”**,但是有狗提议改把a和b的数字的长度改到1e5,使得NXY卡了一下py(

思路:

需要用到的知识点有两个:

  • unsigned long long自然溢出等价于对 2 64 2^{64} 264 取模,也就是说自然溢出啥事没有!
  • ( a × b + c )   %   p = ( ( a × b )   %   p + c   %   p )   %   p (a\times b + c)\ \%\ p = ((a\times b)\ \%\ p+c\ \%\ p)\ \%\ p (a×b+c) % p=((a×b) % p+c % p) % p

因此我们只需要把输入的数 a a a 分解为 a = x ∗ 10 + c a = x * 10 + c a=x∗10+c即可

NXY 特意卡了 python

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef pairpii;

#define MAX 300000 + 50
string s;
ull a, b;

void work(){cin >>s;
    a = b = 0;
    for(auto x : s){a = a * 10 + (ull)(x - '0');
    }
    cin >>s;
    for(auto x : s){b = b * 10 + (ull)(x - '0');
    }
    cout<< (ull)(a+b)<io;
    work();
    return 0;
}
Problem H 柳予欣的色图【Pólya 计数】

出题人: BHQ

防AK题

题目描述:

一个手链上有 n n n 个珠子,有 n n n 种颜色,给每个珠子都染上颜色。有多少种不同的染色方法。由于方案数很多,请对 998244353 998244353 998244353 取模。

题解

Pólya 计数的裸题,很难,想了解可以自己了解。

#include#include#include#include#include#include#include#include
#include#includeusing namespace std;
#define ll long long
const int N = 1e4+5;
const ll mod = 998244353;

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

ll phi(ll n){ll ans = n;
    for(int i = 2; i*i<= n; ++i){if(n % i == 0){ans = ans / i * (i-1);
            while(n % i == 0)
                n /= i;
        }
    }
    if(n != 1)
        ans = ans / n * (n-1);
    return ans;
}

void solve(ll n){if(n == 1)
        cout<< 1<< '\n';
    else
    {ll ans = 0;
        for(int i = 1; i * i<= n; ++i){if(n % i == 0){if(i * i == n)
                    ans = (ans + (phi(n/i) * qpow(n, i, mod) % mod)) % mod;
                else{ans = (ans + (phi(i) * qpow(n, n/i, mod) % mod)) % mod;
                    ans = (ans + (phi(n/i) * qpow(n, i, mod) % mod)) % mod;
                }
            }
        }
        cout<< (ans * qpow(n, mod-2, mod)) % mod<< '\n';
    }
}

int main()
{std::ios::sync_with_stdio(false);
    ll n;
    cin >>n;
    solve(n);
	return 0;
}
Problem I WWW的杂货铺【模拟】

出题人: WYY

题目描述:

M条出售记录,每条出售记录由物品名称、收货地、出售数目组成。

请按如下规则进行统计并输出:物品按收货地分类,并合并出售数目,收货地按字典序排列,同一收货地的物品按字典序排列。

思路:

很简单的模拟题,没什么意思

#pragma GCC optimize(3)
#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
string s, t;

struct ran{string s;
    mapmp;
}tr[105];

void work(){cin >>n;
    for(int i = 1; i<= 100;++i)tr[i].mp.clear();
    mapmp;
    int tot = 0;
    for(int i = 1; i<= n; ++i){cin >>s >>t >>x;
        if(!mp.count(t))mp[t] = ++tot;
        tr[mp[t]].s = t;
        tr[mp[t]].mp[s]+=x;
    }
    for(auto [x,y] : mp){cout<< tr[y].s<< endl;
        cout<< "--------------------\n";
        for(auto [u, v] : tr[y].mp){cout<< "    ";
            cout<< u<< "("<io;
    int tt;cin>>tt;
    for(int _t = 1; _t<= tt; ++_t){work();
        if(_t != tt)cout<< endl;
    }
    return 0;
}
Problem J 去玩宝可梦喽~ 【dp+线段树】

出题人: DJK

题目描述:

脱离题干背景,单纯考虑区间操作,发现题意如下:

给你一个长度为 n ( 1 ≤ n ≤ 5 ∗ 1 0 5 ) n(1≤n≤5*10^5) n(1≤n≤5∗105)的数组。你需要将其分成几段连续的子区间,每一段区间的权值如下:

  • 若区间和大于0,则为区间长度
  • 如区间和等于0,则为0
  • 如区间和小于0,则为区间长度的相反数

用一个式子表示即: v a l [ l , r ] = s i g n ( s u m [ l , r ] ) ∗ ( r − l + 1 ) val[l,r] = sign(sum[l,r]) * (r - l + 1) val[l,r]=sign(sum[l,r])∗(r−l+1) ( v a l [ l , r ] 表 示 区 间 [ l , r ] 的 权 值 , s i g n 函 数 同 原 题 中 的 f 函 数 , s u m [ l , r ] 亦 相 同 ) (val[l,r]表示区间[l,r]的权值,sign函数同原题中的f函数,sum[l,r]亦相同) (val[l,r]表示区间[l,r]的权值,sign函数同原题中的f函数,sum[l,r]亦相同)

问你分出来的子区间的权值和大为多少,并且是否大于等于 H H H。

思路

数据结构优化DP

我们首先考虑暴力解法。

定义 d p [ i ] dp[i] dp[i]为 [ 1 , i ] [1,i] [1,i]中的大权值和,容易发现可以 O ( n ) O(n) O(n)转移,总体复杂度需要 O ( n 2 ) O(n^2) O(n2)。

转移方程: d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s i g n ( s u m [ j + 1 , i ] ) ∗ ( i − ( j + 1 ) + 1 ) ) 其 中 ( 0 ≤ j < i ) dp[i] = max(dp[i], dp[j] + sign(sum[j+1,i]) * (i-(j+1)+1)) 其中(0≤j

复杂度过高,我们考虑优化。

根据 s i g n sign sign函数的值分类讨论,化简转移方程:

d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s i g n ( s u m [ i ] − s u m [ j ] ) ∗ ( i − j ) ) dp[i] = max(dp[i],dp[j]+sign(sum[i]-sum[j])*(i-j)) dp[i]=max(dp[i],dp[j]+sign(sum[i]−sum[j])∗(i−j))

若 s u m [ i ] = = s u m [ j ] sum[i]==sum[j] sum[i]==sum[j], d p [ i ] = m a x ( d p [ j ] ) dp[i] = max(dp[j]) dp[i]=max(dp[j])

若 s u m [ i ] > s u m [ j ] sum[i] >sum[j] sum[i]>sum[j], d p [ i ] = m a x ( d p [ j ] − j + i ) dp[i] = max(dp[j] - j +i) dp[i]=max(dp[j]−j+i)

若 s u m [ i ] < s u m [ j ] sum[i]< sum[j] sum[i]

我们只需要求出上述三种情况下对应的 m a x max max,之后这三个值取 m a x max max即可。

容易发现,需要一个支持单点修改+区间查询且复杂度过得去的数据结构来维护。

做法是预处理前缀和,之后离散化,然后按照前缀和建线段树(其他满足条件的数据结构均可)。

即线段树的下标表示 s u m [ j ] sum[j] sum[j],上述的三个大值分别通 q u e r y ( s u m [ i ] , s u m [ i ] ) query(sum[i],sum[i]) query(sum[i],sum[i]), q u e r y ( 1 , s u m [ i ] − 1 ) query(1, sum[i]-1) query(1,sum[i]−1), q u e r y ( s u m [ i ] + 1 , n ) query(sum[i] + 1, n) query(sum[i]+1,n)获得。

复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。

另外,提示中试试暴力是希望先写出暴力转移方程,方便之后的观察优化。

5 e 5 5e5 5e5的数据量暴力是不可能过的。

下面给出利用线段树优化的代码。

#includeusing namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set::iterator
#define pii pairconst int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int t, n, x, h;
int sum[maxn];
int dp[maxn];
vectorvt;
struct node
{int l, r;
    int dp, dp1, dp2;//维护上述的三个大值

    int mid()
    {return (l + r) >>1;
    }

    void print()
    {cout<< l<< ' '<< r<< ' '<< dp<< ' '<< dp1<< ' '<< dp2<< '\n';
    }
} tree[maxn<<2];

void pushup(node &p, node &le, node &ri)
{p.l = le.l;
    p.r = ri.r;
    p.dp = max(le.dp, ri.dp);
    p.dp1 = max(le.dp1, ri.dp1);
    p.dp2 = max(le.dp2, ri.dp2);
}

void pushup(int p)
{pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{tree[p].l = l;
    tree[p].r = r;

    if(l == r)
    {tree[p].dp = tree[p].dp1 = tree[p].dp2 = -inf;
        return ;
    }

    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int pos, int dp, int id)
{if(tree[p].l == tree[p].r)
    {tree[p].dp = max(tree[p].dp, dp);
        tree[p].dp1 = max(tree[p].dp1, dp - id);
        tree[p].dp2 = max(tree[p].dp2, dp + id);
        return ;
    }

    int mid = tree[p].mid();
    if(pos<= mid) updata(p<<1, pos, dp, id);
    else updata(p<<1|1, pos, dp, id);
    pushup(p);
}

node query(int p, int l, int r)
{if(l >r) return {-inf, -inf, -inf, -inf};
    if(l<= tree[p].l && tree[p].r<= r) return tree[p];

    int mid = tree[p].mid();
    if(mid >= r) return query(p<<1, l, r);
    else if(mid< l) return query(p<<1|1, l, r);
    else
    {node le = query(p<<1, l, r);
        node ri = query(p<<1|1, l, r);
        node res;
        pushup(res, le, ri);
        return res;
    }
}

void work()
{vt.clear();
    cin >>n >>h;
    for(int i = 1; i<= n; ++i)
    {cin >>x;
        sum[i] = sum[i - 1] + x;
        vt.push_back(sum[i]);
        dp[i] = 0;
    }
    vt.push_back(0);

    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());

    build(1, 1, vt.size());

    node pp;
    int mx1, mx2, mx3, pos;
    pos = lower_bound(vt.begin(), vt.end(), 0) - vt.begin() + 1;
    updata(1, pos, 0, 0);
    for(int i = 1; i<= n; ++i)
    {pos = lower_bound(vt.begin(), vt.end(), sum[i]) - vt.begin() + 1;
        mx1 = query(1, 1, pos - 1).dp1;
        mx2 = query(1, pos, pos).dp;
        mx3 = query(1, pos + 1, vt.size()).dp2;
        dp[i] = max(mx1 + i, max(mx2, mx3 - i));
        updata(1, pos, dp[i], i);
    }

    cout<< dp[n]<< ' '<< (dp[n] >= h)<< '\n';
}

signed main()
{io;
    cin >>t;
    while(t--) work();
    return 0;
}
Problem K 逃出虚圈!【bfs】

出题人: LYJ

出了一个bfs的模版题,没人做,好伤心,写了半天的题目背景,没人看,好伤心,甚至在赛时加了一个小彩蛋,也没人看,好伤心

虽然

题目描述:

n个点,m条边,无向图

给你p个起点,q个终点,问你从任意一个起点出发,到达任意一个终点需要的最短距离是多少

思路:

bfs就行,把起点都塞进队列里面,然后记录q个终点,跑的时候遇到第一个出现的终点的时候就是最短的

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 1000000 + 50
int n, m, k, x, y, a, b;
vectorG[MAX];

queueq;
setse;
int dis[MAX];

void bfs(){while(!q.empty()){int u = q.front();q.pop();
        if(se.count(u)){cout<< dis[u]<< endl;
            return;
        }
        for(auto v : G[u]){if(dis[v] != inf)continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
    cout<< "N0"<< endl;
}

void work(){cin >>n >>m;
    for(int i = 1; i<= m; ++i){cin >>x >>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    mem(dis, inf);
    cin >>a >>b;
    for(int i = 1; i<= a; ++i){cin >>x;
        q.push(x);
        dis[x] = 0;
    }
    for(int i = 1; i<= b; ++i){cin >>x;
        se.insert(x);
    }
    bfs();
    
}

int main(){work();
    return 0;
}
Problem L 为爱发电的Oier【简单期望】

出题人: WWY

签到题,没人写,6

题目描述:

我们可以把题目理解成抛硬币,问期望抛多少次可以使得正面朝上的次数是n

思路:

显然,期望抛2次,可以使得正面朝上的次数是1

拿n次正面朝上的期望就是2*n

所以输出2*n就行

这里有一个很有意思的事情:

image-20221204200818664

十六分钟的时候就有人看到了这个题,并写出了正解,但是因为他没写输入,所以挂了,(笑死

#pragma GCC optimize(3)
#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){cin >>n;
    cout<< 2 * n<< endl;
}


int main(){io;
    work();
    return 0;
}
Problem M完全不管大一死活【分类讨论】

出题人: LYJ

出题的时候,在这个题前面出了五六个题,没有一个签到题,所以我就放了一个小讨论题

题目描述:

你在0的位置,目标是x的位置,y的位置有一个门,z的位置有一个钥匙,问你最少需要走几步能到x,如果不能到输出-1

思路:

签到题,简单分类一下就行,没什么意思

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout<< "Debuging...|"<< #a<< ": "<< a<< "\n";
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int x, y, z;

void work(){cin >>x >>y >>z;
    if(x == 0){cout<< 0<< endl;
    }
    else if(x >0){if(y< 0 || y >x)cout<< x<< endl;
        else {if(z >y)cout<< "BLEACH yyds"<< endl;
            else{if(z >0)cout<< x<< endl;
                else cout<< -z*2 + x<< endl;
            }
        }
    }
    else{if(y< x || y >0)cout<< -x<< endl;
        else{if(z< y)cout<< "BLEACH yyds"<< endl;
            else {if(z >0)cout<< 2*z - x<< endl;
                else cout<< -x<< endl;
            }
        }
    }
}


int main(){io;
    work();
    return 0;
}
Problem N 泷1千0(easy version)【构造】

出题人: DJK

题目描述:

给你两个字符串 s , t s,t s,t,按照给定的操作方式,是 s s s串变成 t t t串,要求在 3 ∗ n 3*n 3∗n次内完成( n n n是字符串的长度)。

思路:

给出其中一种构造方式。

我们希望当 s 串 与 t 串 s串与t串 s串与t串在位置 i i i不同时,我们希望取反第 i i i个元素且不影响其他元素,这样就可以 O ( n ) O(n) O(n)遍历一遍。

容易发现,取反和反转都拥有一个特征。即对一个01串取反或反转偶数次,字符串不变。

由此,我们即可实现取反第 i i i个位置,而不影响其他元素。

当 s 串 与 t 串 s串与t串 s串与t串在位置 i i i不同时,进行如下操作:

  • 执行操作 i i i
  • 执行操作 1 1 1
  • 执行操作 i i i

可以发现,至多需要 3 ∗ n 3*n 3∗n次,满足题意。

代码:

#includeusing namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set::iterator
#define pii pairconst int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int n;
string s, t;
int ans[3005];
int sum;

signed main()
{io;
    cin >>s >>t;

    n = s.size();
    sum = 0;
    for(int i = 0; i< n; ++i)
    {if(s[i] != t[i])
        {ans[++sum] = i + 1;
            ans[++sum] = 1;
            ans[++sum] = i + 1;
        }
    }

    cout<< sum<< ' ';
    for(int i = 1; i<= sum; ++i) cout<< ans[i]<< ' ';
    return 0;
}
总结

从出题情况来说,很多签到题没人看,没人做,线上比赛比线下比赛的相比,差距很大,有些同学线上比赛没人监督,就随便写两三个题就跑去玩了,这样很不好…

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


名称栏目:2022SDNU-ACM结训赛题解-创新互联
URL网址:http://jkwzsj.com/article/gioso.html