首页 > 其他分享 >AGC005做题笔记

AGC005做题笔记

时间:2025-01-20 16:44:28浏览次数:1  
标签:... minn AGC005 int sum 笔记 stk 做题 长度

Atcoder Grand Contest 005

A - STring

题目大意

有一个字符串 \(X\) ,它的字符数是偶数。其中一半字符为 "S",另一半字符为 "T"。

现执行以下操作 \(10^{10000}\) 次:

  • 在 \(X\) 中(连续)出现的 ST 子串中,删除最左边的一个。如果没有出现,则不做任何操作。

找出 \(X\) 的最终长度。

解题思路

简单题,考虑维护一个栈。

扫一遍字符串 \(X\),将所有的 "S" 都压进栈,每次遇到一个 "T" 就弹出一个元素。

再维护一个字符串的长度变量,根据栈内元素的变化加减。

int ans=0;
for(int i=0;i<n;i++){
    ans++;
    if(s[i]=='S'){
        stk.push(1);
    }
    else if(!stk.empty()){
        stk.pop();
        ans-=2;
    }
}

cout<<ans<<'\n';

B - Minimum Sum

题目大意

有一个长度为 \(N\) , \(a_1, a_2, ..., a_N\) 的排列组合。

试求: \(\sum _{i=1}^{n} \sum _{j=i}^n \min _{i \leq k \leq j} a_{k}\)

解题思路

有一个很明显的转换,如果一个数可以成为一个区间的最小值,说明它前面没有比它小的元素,后面也没有比它小的元素。

这看上去是一句废话,但实际上就转化为了维护一个单调栈的问题:

  • \(l_i\) 表示 \(a_i\) 左边能到达最远的比 \(a_i\) 大的元素。

  • \(r_i\) 表示 \(a_i\) 右边能到达最远的比 \(a_i\) 大的元素。

  • 那么最终答案就是 \(\sum _{i=1}^{n} (r_i-i)\times (i-l_i) \times a_i\)

\(l_i\) \(r_i\) 就是一个单调栈可以维护的。

for(int i=1;i<=n;i++){
    while(!stk.empty()&&a[stk.top()]>a[i]){
        r[stk.top()]=i;
        stk.pop();
    }
    l[i]=stk.empty()?0:stk.top();
    stk.push(i);
}

int ans=0;
for(int i=1;i<=n;i++){
    ans+=(r[i]-i)*(i-l[i])*a[i];
}

cout<<ans<<'\n';

C - Tree Restoring

题目大意

有一个长度为 \(N\) , \(a_1, a_2, ..., a_N\) 的整数序列,判断是否存在这样一棵树:

树上有 \(N\) 个顶点,编号为 \(1\) 到 \(N\) ,假设每条边的长度为 \(1\) ,对于每个 \(i = 1,2,...,N\),顶点 \(i\) 与离它最远的顶点之间的距离为 \(a_i\)。

解题思路

考虑将最长距离直接拆成一条链,然后讨论其中点的位置与个数,记录下 \(a_i\) 中的最小和最大值,进行极值判断。

还要对中点的个数进行判断,偶数长度的链,有两个中点,奇数长度的链,有一个中点,如果不对,说明不可行。

其次,我们注意到中点两边的点的中点个数应该大于 \(2\)。

check 函数:

void check(vector<int> &f,int Max){
	for(int i=(Max+1)/2+1;i<=Max;i++){	
		if(f[i]<2){	
			cout<<"Impossible\n";
			return ;
		}
	}
	cout<<"Possible\n";
}
int maxn=0,minn=1<<30;

vector<int> a(n+5),f(n+5,0);
for(int i=1;i<=n;i++){
    cin>>a[i];
    f[a[i]]++;
    maxn=max(maxn,a[i]);
    minn=min(minn,a[i]);
}

if(minn<(maxn+1)/2){
    cout<<"Impossible\n";
    return 0;
}

if(maxn&1){						
    if(f[(maxn+1)/2]!=2){		
        cout<<"Impossible\n";	
        return 0;
    }
    check(f,maxn);
}
else {				
    if(f[maxn/2]!=1){			
        cout<<"Impossible\n";
        return 0;
    }
    check(f,maxn);
}

D - ~K Perm Counting

题目大意

有一个长度为 \(N\) 的排列,满足以下条件:

  • 假设该排列为 \(a_1, a_2, ..., a_N\) 。对于每个 \(i = 1,2,...,N\) , \(|a_i - i| \neq K\) .

在长度为 \(N\) 的 \(N!\) 个排列中,有多少个满足这个条件?

答案对 \(924844033\) 取模。

解题思路

自己做的时候没有想到 dp,只能打了暴力。

正难则反,考虑容斥。

记 \(f_i\) 表示至少有 \(i\) 个位置不满足条件的方案数,答案为 \(\sum _{i=0}^{n} (-1)^i \times f_i\)

这里需要用到这条性质:对于每个数,与它的差的绝对值为 \(k\) 的数不超过 \(2\) 个。

因此,如果再 \(x\) 和 \(x+k\) 之间连边,就会形成 \(k\) 条链,每个点只能和与它有相连的边配对。

vector<vector<array<array<int,2>,2> > > f(n+1,vector<array<array<int,2>,2> >(n+1));

int tot=0;
for(int i=1;i<=n;i++){
    if(!vis[i]){
        for(int j=i;j<=n;j+=k){
            vis[j]=1;
            a[++tot]=j;
        }
    }
}

f[0][0][0][0]=1;
a[0]=-(1<<30);

for(int i=1;i<=n;i++){
    f[i][0][0][0]=1;
    for(int j=1;j<=i;j++){
        f[i][j][0][0]=(f[i-1][j][1][0]+f[i-1][j][0][0]+(a[i]-a[i-1]==k)*f[i-1][j-1][0][0])%mod;
        f[i][j][0][1]=(a[i+1]-a[i]==k)*(f[i-1][j-1][1][0]+f[i-1][j-1][0][0])%mod;
        f[i][j][1][0]=(f[i-1][j][0][1]+f[i-1][j][1][1]+(a[i]-a[i-1]==k)*f[i-1][j-1][0][1])%mod;
        f[i][j][1][1]=(a[i+1]-a[i]==k)*(f[i-1][j-1][0][1]+f[i-1][j-1][1][1])%mod;
    }
}

for(int i=0;i<=n;i++){
    int sum=(f[n][i][0][0]+f[n][i][0][1]+f[n][i][1][0]+f[n][i][1][1])%mod;
    if(i&1){
        ans=(ans+mod-sum*fac[n-i]%mod)%mod;
    }
    else{
        ans=(ans+sum*fac[n-i]%mod)%mod;
    }
}

标签:...,minn,AGC005,int,sum,笔记,stk,做题,长度
From: https://www.cnblogs.com/Sunbutstfan1106/p/18681834

相关文章

  • AI大模型-提示工程学习笔记9-生成知识提示
    卷首语:我所知的是我自己非常无知,所以我要不断学习。写给AI入行比较晚的小白们(比如我自己)看的,大神可以直接路过无视了。有一种改进大语言模型(LLM)推理能力的技术:生成知识作为提示的一部分。这种方法由Liu等人(2022)提出,旨在通过让模型先生成相关知识,再将这些知识整合到推理过......
  • Python Playwright学习笔记(二)
    一、模拟手机playwright.devices可以配置模拟器。importasynciofromplaywright.async_apiimportasync_playwrightasyncdefrun(playwright):iphone_12=playwright.devices['iPhone12']browser=awaitplaywright.webkit.launch(headless=False)conte......
  • uos 开发笔记
    versionGLIBCXX_3.4.26notfound的问题解决一查看是否有这个库/lib64/libstdc++.so.6二查看这个库/lib64/libstdc++.so.6中的的GLIBCXX的支持的版本 经查看是环境里已经有这个库,并且是个软连接,软连接到libstdc++.so.6.0.19 查看这个库/lib64/libstdc++.so.6中的的GLIBCX......
  • Maui学习笔记-系统主题切换
    Maui提供了一种根据当前应用程序主题设置属性的机制,但是它不包含用于在UI中切换主题的组件,需要我们自行创建。创建项目 首先创建一个ThemeInfo类来存储应用程序主题对象及标题。这些对象会在Picker元素中显示。添加CommunityToolkit.Mvvm工具包,创建一个ThemeSettings主......
  • 阅读笔记二
    团队管理与协作的艺术核心内容摘要:团队角色与职责:分析了软件开发团队中常见的角色,如项目经理、产品经理、开发人员、测试人员等,并讨论了各自的责任和协作方式。沟通与合作:强调了有效的沟通对于团队成功的关键作用,介绍了面对面会议、邮件、即时通讯等多种沟通渠道的选择与运用。......
  • JavaScript笔记APIs篇02——DOM事件
     黑马程序员视频地址:黑马程序员前端JavaScript入门到精通全套视频教程https://www.bilibili.com/video/BV1Y84y1L7Nn?vd_source=0a2d366696f87e241adc64419bf12cab&spm_id_from=333.788.videopod.episodes&p=78 目录事件监听(绑定)事件监听其他版本(了解)事件类型事件对象......
  • 圆方树学习笔记
    元方树。下文除特殊强调外,所有图皆为无向图。引入割点:在图中,删除某个点后,导致图不再连通的点。点双连通:在一张图中,取两个点\(u\)、\(v\),无论删去哪个点(除\(u\)、\(v\)自身外),\(u\)、\(v\)都能连通,我们就说\(u\)和\(v\)点双连通。点双连通分量(后文称点双):对于一个无向......
  • 【AIGC-ChatGPT提示词】心灵笔记:打造温暖治愈的职场年终回顾系统
    感谢信任,专栏出现0-1的历史突破❤️❤️好了,开始今天的内容今天继续回馈大家,最近都是可以在自媒体上使用的提示词。提示词在最下方引言在每年岁末时分,我们都期待着对过去一年进行总结与回顾。然而,传统的工作总结往往过于注重数据和绩效,容易忽视个人的情感体验和内心成长......
  • AC 自动机 学习笔记
    耳机声音疑似有点小了,用心旷神怡的话来说大致会是「比果蝇↑嗡嗡声还小」。说到这个就不得不说到年级\(1200-7\)个人生物考不过我一个裸考的,还是有点吓人的。博主为什么不分享一下自己的数学成绩呢,是不屑吗......
  • WebRTC 笔记
    目录通话建立流程特别提醒代码创建 RTCPeerConnection 对象获取本地摄像头/麦克风创建发起方会话描述对象(createOffer)连接的远程对等方属性(setRemoteDescription)建立一条最优的连接方式WebRTC允许网络应用或者站点,在不借助中间媒介的情况下,建立浏览器之间点对点(Peer-to-Peer)的......