当前位置:网站首页>【自娱自乐】构造笔记 week 2
【自娱自乐】构造笔记 week 2
2022-04-23 15:44:00 【来点蕾蒂西亚】
Day 1
1659D Codeforces Round #782 (Div. 2) Reverse Sort Sum
挺有意思的题
已知C数组去构造A数组
一个很显然的废话所有不被判断为0的点都是1。所以只需要判定当前节点或后继节点是不是0就好了。
还有一个很显然的废话,一个点最终为0或1,只有可能是被最终状态下某个0或1更新。抽屉原理,也就是把被推理出为0的点排除,就只能是1了。
当前节点没有被更新,那么判断0或1的手段是判断该点a[i]是否为0。
假设当前点为1,他想要被更新,则只能被0更新,这个不难发现。并且会发现只能被后继的0更新,且这个0是第a[i]+1个点。则我们得到了如果当前点是1,找到后继0的方法。
假设当前点为0,那么他可能中途变成1最后又变成0,也可能一直变成1,也可能不被更新。只讨论被后继0再次更新的情况。我们发现n-a[i]是当前节点i成为0的时间。那么(n-a[i])-(i-1)是被后继权值为0节点更新再次为0的时间,可以判断后继节点的位置是n-((n-a[i])-(i-1))+1==a[i]+i。同时发现一个很无聊的东西只要a[i]+i在n范围内则该点最终结果是0。
我们得到了任何情况下判定当前节点或后继是0的情况,其他情况都是1了
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int st[maxn],a[maxn];
void solve()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)st[i]=-1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
if(st[i]==-1)
{
if(a[i]==0)st[i]=0;
else
{
st[i]=1;
if(st[a[i]+1]==-1)
st[a[i]+1]=0;
}
}
else if(st[i]==0)
{
if(st[a[i]+i]==-1)
st[a[i]+i]=0;
}
}
for(int i=1;i<=n;i++)
printf("%d%c",st[i]," \n"[i==n]);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
solve();
}
}
Codeforces Round #764 (Div. 3) E. Masha-forgetful
哈希,挺暴力的
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e3+10;
int f[maxn];
struct Node
{
int l,r,p;
Node(){l=r=p=0;}
};
Node get(int l,int r,int p)
{
Node x;x.l=l,x.r=r,x.p=p;
return x;
}
void solve()
{
map<string,Node> mp;
int n,m;scanf("%d%d",&n,&m);
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j+1<(int)s.size();j++)
mp[s.substr(j,2)]=get(j,j+1,i);
for(int j=0;j+2<(int)s.size();j++)
mp[s.substr(j,3)]=get(j,j+2,i);
}
cin>>s;
for(int i=1;i<=m;i++)f[i]=0;
f[0]=1;
for(int i=2;i<=m;i++)
{
if(i>=3&&f[i-3]&&mp.find(s.substr(i-3,3))!=mp.end())f[i]=3;
else if(i>=2&&f[i-2]&&mp.find(s.substr(i-2,2))!=mp.end())f[i]=2;
}
if(!f[m]){printf("-1\n");return ;}
vector<Node> res;
int p=m;
while(p){res.push_back(mp[s.substr(p-f[p],f[p])]);p-=f[p];}
reverse(res.begin(),res.end());
printf("%d\n",res.size());
for(auto [l,r,p]:res)
printf("%d %d %d\n",l+1,r+1,p);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
solve();
}
}
Educational Codeforces Round 119 (Rated for Div. 2)D. Exact Change
暴力,不过我没想到,我太菜了
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
int a[maxn];
typedef long long ll;
int get(int n,int d1,int d2)
{
int res=0;
for(int i=1;i<=n;i++)
{
int t=0x3f3f3f3f;
for(int j=0;j<=d1;j++)
for(int k=0;k<=d2;k++)
{
int r=a[i]-j-2*k;
if(r<0)break;
if(!(r%3))t=min(t,r/3);
}
res=max(res,t);
}
return res+d1+d2;
}
void solve()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int res=0x3f3f3f3f;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)res=min(res,get(n,i,j));
printf("%d\n",res);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
solve();
}
}
版权声明
本文为[来点蕾蒂西亚]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_56691888/article/details/124322339
边栏推荐
- PHP operators
- 网站压测工具Apache-ab,webbench,Apache-Jemeter
- PHP PDO ODBC将一个文件夹的文件装载到MySQL数据库BLOB列,并将BLOB列下载到另一个文件夹
- 多生成树MSTP的配置
- Explanation of redis database (IV) master-slave replication, sentinel and cluster
- Sorting and replying to questions related to transformer
- Basic concepts of website construction and management
- 携号转网最大赢家是中国电信,为何人们嫌弃中国移动和中国联通?
- Cookie&Session
- pywintypes.com_error: (-2147221020, ‘无效的语法‘, None, None)
猜你喜欢
For examination
Today's sleep quality record 76 points
Explanation 2 of redis database (redis high availability, persistence and performance management)
APISIX jwt-auth 插件存在错误响应中泄露信息的风险公告(CVE-2022-29266)
携号转网最大赢家是中国电信,为何人们嫌弃中国移动和中国联通?
Application of Bloom filter in 100 million flow e-commerce system
MySQL Cluster Mode and application scenario
Why is IP direct connection prohibited in large-scale Internet
多生成树MSTP的配置
Neodynamic Barcode Professional for WPF V11. 0
随机推荐
2022年中国数字科技专题分析
One brush 314 sword finger offer 09 Implement queue (E) with two stacks
Node.js ODBC连接PostgreSQL
JVM-第2章-类加载子系统(Class Loader Subsystem)
GFS distributed file system (Theory)
网站压测工具Apache-ab,webbench,Apache-Jemeter
IronPDF for . NET 2022.4.5455
Redis主从复制过程
怎么看基金是不是reits,通过银行购买基金安全吗
IronPDF for .NET 2022.4.5455
计算某字符出现次数
What if the package cannot be found
PHP 的运算符
Extract non duplicate integers
什么是CNAS认证?CNAS认可的软件测评中心有哪些?
API IX JWT auth plug-in has an error. Risk announcement of information disclosure in response (cve-2022-29266)
Timing model: gated cyclic unit network (Gru)
MySQL集群模式與應用場景
字节面试 transformer相关问题 整理复盘
Upgrade MySQL 5.1 to 5.67