技术标签: dfs 算法 c++ 树结构 # 算法多校训练 动态规划求解 # ACM特殊算法
什么,你问我维森莫有的题目不能AC,那我告诉你,下面这个骂的就是我!
样例输入
【样例1】 1 1
【样例2】 1 4
【样例3】 7 5
样例输出
【样例1】 1001 -1001
【样例2】 -8 -6 -9 120 -97
【样例3】 323 -320 411 206 -259 298 -177 -564 167 392 -628 151
提示
样例1解释
A sequence (1001,−1001) contains A=1 positive integer and B=1 negative integer totaling 1001+(−1001)=0. It also satisfies the other conditions and thus is a god sequence.
样例2解释
A sequence (−8,−6,−9,120,−97) contains A=1 positive integer and B=4 negative integers totaling (−8)+(−6)+(−9)+120+(−97)=0. It also satisfies the other conditions and thus is a god sequence.
签到题,模拟
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,ans=0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
if(n==m)
for(int i=1; i<=n; i++)
cout << i << " " << i*(-1) << " ";
else if(n>m)
{
for(int i=1; i<=m-1; i++)
cout << i << " " << i*(-1) << " ";
for(int i=m; i<=n; i++) {
cout << i << " ";
ans += i;
}
cout << ans*(-1);
}
else
{
for(int i=1; i<=n-1; i++)
cout << i << " " << i*(-1) << " ";
for(int i=n; i<=m; i++) {
cout << i*(-1) << " ";
ans += i;
}
cout << ans << endl;
}
return 0;
}
样例输入
【样例1】 2 1 2
【样例2】 6 5 3 4 1 5 2
【样例3】 7 314 159 265 358 979 323 846
样例输出
【样例1】 4
【样例2】 32
【样例3】 492018656
提示
样例1解释
There are four possible combinations of heights of the buildings, as follows:
(Building 1, Building 2) = (0,0) (Building 1, Building 2) = (0,1)
(Building 1, Building 2) = (1,1) (Building 1, Building 2) = (1,2)
样例3解释
There are 20192492160000 possible final sceneries. The correct output is that number modulo 109+7, which is 492018656.
除了不同的数会变得相同,其他相对大小不会改变。
设高度取值(包括最低点 0)排序后的集合为 a,独立选择把每个间距(ai+1−ai)减到多少,
答案就是 ∏(ai+1−ai+1)。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e9+7,N=1e5;
int n,a[N],res;
struct op {
int x;
op(int x):x(x) {
}
friend op operator + (const op &a, const op b) {
const int x = a.x+b.x;
return op(x>=M?x-M:x);
}
friend op operator - (const op &a, const op b) {
const int x = a.x-b.x;
return op(x<0?x+M:x);
}
friend op operator * (const op &a, const op b) {
return op(1ll*a.x*b.x%M);
}
};
int ok(int a, int x=M-2, int res=1) {
for(; x; x>>=1, a=(op(a)*a).x)
if(x&1) res=(op(res)*a).x;
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=0; i<n; ++i)
cin>>a[i];
sort(a,a+n), n = unique(a,a+n)-a;
res = a[0]+1;
for(int i=0; i<n-1; ++i)
res = (op(res)*(a[i+1]-a[i]+1)).x;
cout<<res<<endl;
return 0;
}
样例输入
【样例1】 3 BWR
【样例2】 4 RRBB
【样例3】 6 BWWRBW
【样例4】 8 WWBRBBWB
【样例5】 21 BWBRRBBRWBRBBBRRBWWWR
样例输出
【样例1】 W
【样例2】 W
【样例3】 B
【样例4】 R
【样例5】 B
提示
样例1解释
In this case, we will pile up blocks as follows: the 1-st and 2-nd blocks from the left in the bottom row are respectively blue and white, so we place a red block on top of it;
the 2-nd and 3-rd blocks from the left in the bottom row are respectively white and red, so we
place a blue block on top of it;
the blocks in the 2-nd row from the bottom are respectively red and blue, so we place a white block on top of it. Thus, the block at the top will be white;
we should print W.样例2解释
In this case, we will pile up blocks as follows:
the 1-st and 2-nd blocks from the left in the bottom row are both red, so we place a red block on top of it;
the 2-nd and 3-rd blocks from the left in the bottom row are respectively red and blue, so we place
a white block on top of it;
the 3-rd and 4-th blocks from the left in the bottom row are both blue, so we place a blue block on top of it;
the 1-st and 2-nd blocks from the left in the 2-nd row from the bottom are respectively red and white, so we place a blue block on top of it;
the 2-nd and 3-rd blocks from the left in the 2-nd row from the bottom are respectively white and blue, so we place a red block on top of it;
the blocks in the 3-rd row from the bottom are respectively blue and red, so we place a white block on top of it. Thus, the block at the will be white;
we should print W.
公式转换:a⊗b=−(a+b)mod3
组合数算贡献即可。处理阶乘时如果 n≥3,就会 n!≡0(mod3)
所以维护一个数的同时维护它当中因数 3 的个数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5,M=3;
string s;
int n,res;
struct op {
int x;
op(int x):x(x) {
}
friend op operator + (const op &a, const op b) {
const int x = a.x+b.x;
return op(x>=M?x-M:x);
}
friend op operator - (const op &a, const op b) {
const int x = a.x-b.x;
return op(x<0?x+M:x);
}
friend op operator * (const op &a, const op b) {
return op(1ll*a.x*b.x%M);
}
};
int ok(int a, int x=M-2, int res=1) {
for(; x; x>>=1, a=(op(a)*a).x)
if(x & 1) res=(op(res)*a).x;
return res;
}
struct par {
int p,c;
par(int x):p(x),c(0) {
while (!(p%M)) {
p/=M,++c;} }
};
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>s;
par f=1;
for(int i=0; i<n; i++) {
int x = s[i]=='B'?0:(s[i]=='W'?1:2);
if(!f.c) res = (res+op(f.p)*x).x;
if(i==n-1) break;
par m = n-1-i, d=i+1;
f.p = (op(f.p)*m.p*ok(d.p)).x;
f.c = f.c+m.c-d.c;
}
if(!(n&1)) res = (op(0)-res).x;
cout<<(res==0?'B':(res ==1?'W':'R'))<<endl;
return 0;
}
无根树必须找根。必然有一个点 u 满足 Eu=1,就设它为根。
对于两条叶子到根的链,它们受到根的距离的约束必然没有互相之间距离的约束大,但是又不足以大到要把 Eu 跟深度反着标。所以标法必然是维护一个时间,DFS 整棵树,在一个节点进栈的时候时间 +1,出栈的时候时间 +1,然后一个节点的 Eu 为进栈时间。
会发现最大的标号的节点(终止节点) v 的标号是 2n−dep[v]。所以根和终止节点取直径的两端即可。
#include <bits/stdc++.h>
#define ll long long
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
using namespace std;
const int N = 200000+10;
int n,d[N],rt,h[N],a[N],ia=1;
vector<int> G[N];
void bfs(int s) {
for(int u=0; u<n; u++) d[u]=-1;
queue<int> q;
q.push(s), d[s]=0;
while(sz(q)) {
int u = q.front();
q.pop();
for(const int &v : G[u]) {
if(!~d[v])
d[v] = d[u]+1, q.push(v);
}
}
}
void GetH(int u, int fa=-1) {
h[u]=-1;
for(const int &v : G[u]) {
if(v!=fa)
GetH(v,u), h[u]=max(h[u],h[v]);
}
++h[u];
}
void GetA(int u, int fa=-1)
{
a[u] = ia++;
for(const int &v:G[u])
if(v!=fa) GetA(v,u);
++ia;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=0; i<n-1; i++) {
int u,v;
cin>>u>>v,--u,--v;
G[u].push_back(v), G[v].push_back(u);
}
bfs(0), rt = max_element(d,d+n)-d;
GetH(rt);
for(int u=0; u<n; u++) {
sort(all(G[u]), [&](const int &i, const int &j) {
return h[i] < h[j];});}
GetA(rt);
for(int u=0; u<n; u++)
cout<<a[u]<<' ';
cout << endl;
return 0;
}
样例输入
【样例1】 1 1
【样例2】 2 3
【样例3】 3 7
【样例4】 8 24
【样例5】 30 230
【样例6】 25 455
样例输出
【样例1】 2
【样例2】 2
【样例3】 6
【样例4】 568
【样例5】 761128315856702
【样例6】 0
注意数组大小!容我偷个题解…
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll ans,c[62][62],f[62][62*62][62];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<65; i++) {
c[i][0] = c[i][i]=1;
for(int j=1; j<i; j++)
c[i][j] = c[i-1][j-1]+c[i-1][j];
}
for(int i=1; i<=n+1; i++)
f[i][c[i][2]][i-1] = 1;
for(int i=1; i<=2*n+1; i++)
for(int j=0; j<=m; j++)
for(int k=0; k<i; k++)
for(int x=k+2; x<=2*n+1-i; x++)
if (j+c[x][2]<=m)
f[i+x][j+c[x][2]][x-(k+2)] += c[x-1][k+1]*f[i][j][k];
for(int i=1; i<=2*n+1; i++)
for(int j=0; j<=m; j++)
for(int k=1; k<i; k++)
for(int x=k; x<=2*n+1-i; x++)
if (j+c[x][2]<=m)
f[i+x][j+c[x][2]][x-k] += c[x-1][k-1]*f[i][j][k];
printf("%lld",ans+f[2*n+1][m][0]);
return 0;
}
sort一下,二分
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10;
int n,k,maxn,a[N];
int main()
{
cin>>n>>k;
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
{
int l=i,r=n;
while(l<r)
{
int mid=(l+r+1)/2;
if(a[mid]<=a[i]+k) l=mid;
else r=mid-1;
}
maxn=max(maxn,l-i+1);
}
cout<<maxn<<endl;
return 0;
}
这提示给的,难度直接降到最低…直接分类讨论
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a,b,c,t;
int main()
{
cin>>a;
if(a!=6) cout<<"0"<<endl;
else if(a==6)
{
cin>>b;
if(b!=6) cout<<"10"<<endl;
else {
cin>>c;
if(c!=6) cout<<"100"<<endl;
else cout<<"1000"<<endl;
}
}
return 0;
}
文章浏览阅读1k次。题意:求在一定l时间内看完n中电影中的m是否可能,若可能则最后快乐度是多少。之前错了好多遍,一直找不到原因,后来在百度上看了很多别人的代码发现只有初始化不同我的初始化: memset(f,0,sizeof(f));别人的: for(int i=0;i for(int j=0;j一开始认为没什么影响,但是苦于一直找不到原因,所以我将自_hdu - 3496
文章浏览阅读2k次。下面可以不看,一句话,为了其安全起见,以后我们就用SecurityRandom就好了。JDK中有两个随机数类。一个是PRNG,也就伪随机数类java.util.Random,是采用线性同余算法产生的。另一个是RNG,也就是java.util.Random的子类强随机数java.security.SecureRandom,这是一个SPI类,也就是说具体的算法由Pro..._securerandom和math.random()
文章浏览阅读8k次,点赞8次,收藏8次。npm安装vue报错npm ERR! code ETIMEDOUT_code etimedout
文章浏览阅读5k次。这两天用阿里云服务器重新部署网站服务器后,打开某php页面出现了如下警告:Warning: mysql_connect(): Headers and client library minor version mismatch. Headers:50547 Library:50631 in /XXX(某某目录)/wp-db.php on line 1520,虽然是警告,但是有的界面会因此打不开,无法..._mysql headers:50647
文章浏览阅读17次。它提供了丰富的功能和工具,帮助开发者编写高效且易于维护的代码。Maven 是一种流行的项目管理工具,用于构建和管理 Java 项目的依赖关系。Eclipse 是另一个受欢迎的 Java IDE,被广泛用于后端开发。每个工具都有其独特的优势和适用场景,开发者可以根据自己的需求和偏好选择合适的工具。这些工具的使用可以提高开发效率、简化开发流程,并改善代码的可维护性和可读性。Java是一种广泛使用的编程语言,用于开发各种类型的应用程序,包括后端服务。在Java开发中,使用合适的工具可以提高开发效率和代码质量。
文章浏览阅读156次。一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。思路:当n=1时,f(1)=1当n=2时,f(2)=2当n=3时,第一步可以跳一阶,剩下的是f(2);或者第一步可以跳两节,剩下的是f(1)。即f(3)=f(2)+f(1)…当n阶台阶,第一步可以跳一阶,剩下的是f(n-1);或者第一步可以跳两节,剩下的是f(n-2);第一步可..._牛客网青蛙跳台阶
文章浏览阅读97次。解压缩各种安装程序包文:tracky来源:http://bbs.hanzify.org/index.php?showtopic=24638&hl=点击:2578解压缩各种安装程序包1 微软的Installer制作的安装包,后缀一般是msi,mspA 可以用totalcmd 的msiplus插件,可以解压。不可以修改msi。B 可以用WinINSTALL LE 2003,在w..._php软件压缩包安装
文章浏览阅读295次。2023年我们进入了AI2.0时代。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义,不亚于互联网和个人电脑的问世。360创始人周鸿祎认为未来各行各业如果不能搭上这班车,就有可能被淘汰在这个数字化时代,如何能高效地处理文本、文献查阅、PPT编辑、编程、绘图和论文写作已经成为您成功的关键。而 ChatGPT,作为一种强大的自然语言处理模型,具备显著优势,能够帮助您在各个领域取得突破。ChatGPT 在论文写作与编程方面也具备强大的能力。_最新chatgpt/gpt4科研技术应用与ai绘图及论文高效写作
文章浏览阅读2.5k次。NginxNginx服务器基础配置实例Nginx服务操作的问题Nginx配置成系统服务Nginx命令配置到系统环境Nginx静态资源部署Nginx静态资源概述Nginx静态资源的配置指令listen指令default_server说明server_name指令配置方式一:精确匹配配置方式二:使用通配符配置配置三:使用正则表达式配置匹配执行顺序server_name总结location指令设置请求资源的目录root / aliasindex指令error_page指令静态资源优化配置语法sendfile,用来开_nginx静态资源释放
文章浏览阅读2.9w次,点赞2次,收藏4次。有一天,上网查查Android的知识点(我是初学者),不经意的碰到黑苹果这个概念,因为没用过白苹果,所以有个想折腾的想法,于是从此深入大坑。教程是网上的,是用TransMac格式化的U盘,后面折腾了半天,启动卡在苹果LOGO,生命在于折腾。我不怕。。。。。—___—这个是题外话了。后面因为要用到U盘(不是黑苹果的事了),突然发现U盘用不了了,格式化也不行,用DG也不行(有人说可以),然后网上找..._transmac格式化u盘导致无法读取
文章浏览阅读3k次。一、maya模型通过mixamo绑定后,发现有模型重叠需要删改,在Maya中删除后导出fbx后总是空集。发现是个fbx导出问题,MAYA做了动画的模型导出FBX,动画好好的,但部分模型没了???【maya吧】_百度贴吧这样操作后会取消蒙皮绑定,于是我去blender里 通过betterfbx插件导入,在编辑模式中删除了多余模型,之后再betterfbx导出,fbx模型绑定都在,进入unity也没问题,应该就是个Mayafbx插件问题。(小白见解)二、..._blender怎么解除蒙皮
文章浏览阅读4.1w次。遥控小车是每个人童年的最爱,不仅好奇它的奇妙,更是喜欢它带来的刺激。小编为大家带来几篇博客,来给大家讲讲制作遥控小车的程序。看大标题可知我们一共有五个方法去制作一款带有遥控功能的小车,小编分开来给大家讲解。本文为基于arduino的手机蓝牙遥控小车基于arduino的手机蓝牙遥控小车基于arduino的红外遥控小车基于arduino的无线NRF24L01遥控小车基于ardu..._sumjess