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
Problem B 收收心找个电子厂上班了【区间贪心/差分约束】出题人: LYJ
很可惜,赛时并没有人过这个题
题目描述:思路1给你m种条件
(l[i],r[i],c[i])
,要求构造一个01串,使得l[i]
到r[i]
中至少有c[i]
个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-1
到r
的权值为c的边,但是为了避免使用0,我们改成l
到r+1
建一条边因为是前缀和,且一个位置最多一个1,所以建立一个
0≤sum[i]-sum[i-1]≤1
的条件,拆开来看就是sum[i]≥sum[i-1]+0
,建一条从i-1
到i
的权值为0的边,sum[i-1]≥sum[i]-1
,建立一条从i
到i-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
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
就行这里有一个很有意思的事情:
十六分钟的时候就有人看到了这个题,并写出了正解,但是因为他没写输入,所以挂了,(笑死
#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结训赛题解-创新互联
标题链接:http://scyanting.com/article/gioso.html