2019 杭电多校（第五场）

2023-11-09 15:49
文章标签 2019 第五场 杭电多校

本文主要是介绍2019 杭电多校（第五场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1002 three arrays

http://acm.hdu.edu.cn/showproblem.php?pid=6625

题意

给你两个数组 让你排序 使他们的对应异或值字典序最小

思路

https://www.bilibili.com/video/av62396512?from=search&seid=2029202226881211707

代码

（调自闭了 请队友帮的忙（01字典树多跑了一位 初始化函数没有调用))

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 1e5+100;
int a[maxn],b[maxn];
int tree[50*maxn][2],tree2[50*maxn][2];
int num[50*maxn],num2[50*maxn];
int tot,tot2,top;
int n;
int ans[maxn];
int qw[40];
void init()
{tot = tot2 = 1;top = 0;tree[0][0] = tree[0][1] = tree2[0][1] = tree2[0][0] = 0;
}
void add(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(tree[u][v] == 0){tree[tot][0] = tree[tot][1] = 0;num[tot] = 0;tree[u][v] = tot++;}u = tree[u][v];num[u]++;}
}
void add2(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(tree2[u][v] == 0){tree2[tot2][0] = tree2[tot2][1] = 0;num2[tot2] = 0;tree2[u][v] = tot2++;}u = tree2[u][v];num2[u]++;}
}void dfs(int x1,int x2,int len,int res,int sum)
{if(len == 31){for(int i = 1;i <= sum;i++){ans[++top] = res;}return ;}int l = num[tree[x1][0]],r = num[tree[x1][1]];int ll = num2[tree2[x2][0]],rr = num2[tree2[x2][1]];if(l>0&&ll>0){int mi = min(l,ll);mi = min(mi,sum);l -= mi,ll -= mi;dfs(tree[x1][0],tree2[x2][0],len+1,res,mi);num[tree[x1][0]] -= mi,num2[tree2[x2][0]] -= mi;}if(r>0&&rr>0){int mi = min(r,rr);mi = min(mi,sum);r -= mi,rr -= mi;dfs(tree[x1][1],tree2[x2][1],len+1,res,mi);num[tree[x1][1]] -= mi,num2[tree2[x2][1]] -= mi;}if(l>0&&rr>0){int mi = min(l,rr);mi = min(mi,sum);l -= mi,rr -= mi;dfs(tree[x1][0],tree2[x2][1],len+1,res^qw[29-len+1],mi);num[tree[x1][0]] -= mi,num2[tree2[x2][1]] -= mi;}if(r>0&&ll>0){int mi = min(r,ll);mi = min(mi,sum);r -= mi,ll -= mi;dfs(tree[x1][1],tree2[x2][0],len+1,res^qw[29-len+1],mi);num[tree[x1][1]] -= mi,num2[tree2[x2][0]] -= mi;}
}
int main()
{int T;scanf("%d",&T);qw[0] = 1;for(int i = 1;i <= 30;i++){qw[i] = qw[i-1]*2;}while(T--){init();int n;scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);add(a[i]);}for(int i = 1;i <= n;i++){scanf("%d",&b[i]);add2(b[i]);}dfs(0,0,1,0,n);sort(ans+1,ans+1+n);for(int i = 1;i <= n;i++){if(i != 1) printf(" ");printf("%d",ans[i]);}printf("\n");}return 0;
}

做法二

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+100;
int tree[maxn*40][2],tree2[maxn*40][2];
int num[maxn*40],num2[maxn*40];
int val[maxn*40],val2[maxn*40];
int tot,tot2,top;
int a[maxn],b[maxn];
map<int,int> mp;
int n;
int ans[maxn];
void init()
{tot = tot2 = 1;top = 0;tree[0][0] = tree[0][1] = tree2[0][0] = tree2[0][1] = 0;mp.clear();
}
void add(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(tree[u][v] == 0){tree[tot][0] = tree[tot][1] = 0;num[tot] = 0;tree[u][v] = tot++;}u = tree[u][v];num[u]++;}val[u] = x;
}
void add2(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(tree2[u][v] == 0){tree2[tot2][0] = tree2[tot2][1] = 0;num2[tot2] = 0;tree2[u][v] = tot2++;}u = tree2[u][v];num2[u]++;}val2[u] = x;
}
int query(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(num[tree[u][v]]){u = tree[u][v];}else u = tree[u][v^1];}return val[u];
}
int query2(int x)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;if(num2[tree2[u][v]]){u = tree2[u][v];}else u = tree2[u][v^1];}return val2[u];
}
int updata(int x,int y)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;u = tree[u][v];num[u]+=y;}
}
int updata2(int x,int y)
{int u = 0;for(int i = 29;i >= 0;i--){int v = (x>>i)&1;u = tree2[u][v];num2[u]+=y;}
}int main()
{ios::sync_with_stdio(false);int T;cin>>T;while(T--){init();cin>>n;for(int i = 1;i <= n;i++){cin>>a[i];add(a[i]);mp[a[i]]++;}for(int i = 1;i <= n;i++){cin>>b[i];add2(b[i]);}int p = 1;int aa,bb,cc;while(p <= n){if(mp[a[p]] == 0){p++;if(p > n) break;continue;}aa = a[p];bb = query2(aa);cc = query(bb);while(cc != aa){aa = cc;bb = query2(aa);cc = query(bb);}ans[++top] = aa^bb;updata(aa,-1);updata2(bb,-1);mp[aa]--;}sort(ans+1,ans+1+n);for(int i = 1;i <= n;i++){if(i != 1) printf(" ");printf("%d",ans[i]);}printf("\n");}return 0;
}

1004 equation （数学）

http://acm.hdu.edu.cn/showproblem.php?pid=6627

题意

给你一个方程 求解

思路

对于绝对值 不同的区间去绝对值后式子不同 即会有（n+1）个求解区间 分别求解即可

代码

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+100;
struct node
{int a,b;double x;int id;
}qw[maxn],ans[maxn];
int a[maxn],b[maxn];
int n, c, A, B;
double l,r;
queue<node> q;
int f;bool cmp(node a,node b)
{if(a.x != b.x) return a.x < b.x;else return a.id < b.id;
}void solve()
{if(A==0&&B == c){f = 1;return ;}double ans;ans = (double)(c-B)/A;if(ans  > l&&ans <= r){int as = 1;if(ans < 0) as = -1;int x = (c - B),y = A;x = abs(x),y = abs(y);int z;if(x == 0) z =  y;else z = __gcd(x,y);node u;u.a = x / z * as,u.b = y / z;q.push(u);}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&c);A = 0,B = 0;for(int i = 1;i <= n;i++){scanf("%d%d",&a[i],&b[i]);qw[i].a = a[i],qw[i].b = b[i];qw[i].id = i;qw[i].x = (double)b[i]/a[i]*(-1.0);A += -a[i],B += -b[i];}sort(qw+1,qw+1+n,cmp);f = 0;while(!q.empty()) q.pop();l = -1e18,r = -1e18;qw[n+1].x = 1e18;for(int i = 1;i <= n+1;i++){l = r,r = qw[i].x;solve();A += qw[i].a*2;B += qw[i].b*2;}if(f) printf("-1\n");else{printf("%d",q.size());while(!q.empty()){node u = q.front();q.pop();printf(" %d/%d",u.a,u.b);}printf("\n");}}return 0;
}

1005 permutation 1 （思维）

http://acm.hdu.edu.cn/showproblem.php?pid=6628

题意

给你n个数  1 到 n  问你全排列相邻差字典序第k大的是哪个

思路

k最大10000 8个数即可 n小于8位之间暴力 大于8位直接填最后8位之前 最大8位暴力

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{int a[30];} qw[1000000];
int vis[30];
int p,n,m;
int xx[30];bool cmp(node a,node b)
{for(int i = 2; i <= m; i++){if(a.a[i]-a.a[i-1]!= b.a[i] - b.a[i-1]){return a.a[i]-a.a[i-1] < b.a[i] - b.a[i-1];}}
}void dfs(int x)
{if(x == m+1){p++;for(int i = 1; i <= m; i++){qw[p].a[i] = xx[i];}return ;}for(int i = 1; i <= n; i++){if(vis[i] == 0){vis[i] = 1;xx[x] = i;dfs(x+1);vis[i] = 0;}}
}int main()
{int T;scanf("%d",&T);while(T--){int k;scanf("%d%d",&n,&k);m = n;p = 0;memset(vis,0,sizeof(vis));if(n <= 8){dfs(1);sort(qw+1,qw+1+p,cmp);for(int i = 1; i <= n; i++){if(i != 1)printf(" ");printf("%d",qw[k].a[i]);}printf("\n");}else{printf("%d",n);vis[n] =1;for(int i = 1; i <= n - 8 - 1; i++){printf(" %d",i);vis[i] = 1;xx[1] = i;}m = 9;dfs(2);sort(qw+1,qw+1+p,cmp);for(int i = 2; i <= m; i++){printf(" %d",qw[k].a[i]);}printf("\n");}}return 0;
}

1006 string matching （扩展kmp）

http://acm.hdu.edu.cn/showproblem.php?pid=6629

题意

给你一个字符串 问从第2位 每一位和字符串相等前缀多长 （比较多少次 直到完全匹配 或 失败）

思路

拓展kmp 注意完全匹配时不需要加一次失败匹配

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef long long ll;
char s[N];
int nex[N],extend[N];
ll sum;
void get_next()
{int len = strlen(s);nex[0] = len;int mx = 0,id;for(int i = 1;i < len;i++){if(i < mx) nex[i] = min(mx-i,nex[i-id]);else nex[i] = 0;while(s[i+nex[i]] == s[nex[i]]) nex[i]++;if(mx < i + nex[i]){id = i;mx = i + nex[i];}sum += (ll)min(nex[i]+1,len-i);}
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",s);sum = 0;get_next();ll n = strlen(s);printf("%lld\n",sum);}return 0;
}

1007 permutation 2

http://acm.hdu.edu.cn/showproblem.php?pid=6630

题意

给你n个数 1-n  给你其中两个做第一和最后 打其他数填到里面 有多少种填法

思路

很容易想到如果第一位不是1 要把1-x-1填成 1 ...... x-1

最后一位不是n n后面要填成  y-1......y

中间就是 dp[i] = dp[i-1] + dp[i-3] 

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll dp[100005];
int main()
{int T;scanf("%d",&T);dp[1] = 1;dp[2] = 1;dp[3] = 1;for(int i = 4;i <= 100000;i++){dp[i] = dp[i-1] + dp[i-3];dp[i] %= mod;}while(T--){ll n,x,y;scanf("%lld%lld%lld",&n,&x,&y);if(x > y) swap(x,y);if(x != 1) x++;if(y != n) y--;printf("%lld\n",dp[y-x+1]);}return 0;
}

 

这篇关于2019 杭电多校（第五场）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/377077。

相关文章

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点：Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点：弱密码字典爆破 四种方法：   [web][极客大挑战 2019]Http 考点：Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩，我们先查看源代码
阅读更多...
2019学习计划

2019学习计划

工作三年了，第一年感觉是荒废的，第二年开始学习python，第三年开始自动化 感觉自己会的东西比较少，而且不够深入，流于表面 现制定一下今年大概的学习计划 需持续巩固加强：python、ui自动化、接口自动化、sql等 代码量需提升，敲的不够（重点） 学习： 1.移动端测试，appium等 2.前端知识系统整理学习  3.性能测试 4.docker入门，环境搭建 5.shell
阅读更多...
最简单的使用JDBC[连接数据库] mysql 2019年3月18日

最简单的使用JDBC[连接数据库] mysql 2019年3月18日

最极简版本的, 我们这里以mysql为例: 首先要创建maven工程, 需要引入jar包:,这里需要注意, 如果你安装的是mysql最新版本8以上的, 下面有些地方需要更改,具体就是mysql连接的url, 和5版本的不一样,具体解决请自行百度哈.这里只演示mysql5版本的? 依赖: <dependency>   <groupId>mysql</groupId>   <artifactId
阅读更多...
(php伪随机数生成)[GWCTF 2019]枯燥的抽奖

(php伪随机数生成)[GWCTF 2019]枯燥的抽奖

审核源码发现加载check.php，审计发现使用了mt_rand()函数，这个函数生成的值是伪随机的 参考下面这篇文章 PHP mt_rand安全杂谈及应用场景详解 - FreeBuf网络安全行业门户 kali里面输入下载工具 git clone https://github.com/openwall/php_mt_seed.git cd进去输入make后编译出的文件先
阅读更多...
2019年2月17日

2019年2月17日

今天又重新看了一下输出第1500个丑数 在我错了八次之后发现要输出一个句号还要输出换行 接下来的两天应该进入复习阶段了。
阅读更多...
National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle

National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle

编辑代码 2000ms 262144K Generalized Pascal's Triangle Pascal's triangle is a triangular array in which each number can be calculated by the sum of the two numbers directly above that number as shown i
阅读更多...
Hinton等人最新研究：大幅提升模型准确率，标签平滑技术 2019-7-8

Hinton等人最新研究：大幅提升模型准确率，标签平滑技术 2019-7-8

导读：损失函数对神经网络的训练有显著影响，也有很多学者人一直在探讨并寻找可以和损失函数一样使模型效果更好的函数。后来，Szegedy 等学者提出了标签平滑方法，该方法通过计算数据集中 hard target 的加权平均以及平均分布来计算交叉熵，有效提升了模型的准确率。近日，Hinton 团队等人在新研究论文《When Does Label Smoothing Help？》中，就尝试对标签平滑技术对
阅读更多...
Photoshop CC 2019圆形的抠图

Photoshop CC 2019圆形的抠图

快速进入矩形选区 快速在矩形和圆形选区之前切换： shift+M 选择的时候，按住shift，可以选中正方形/圆形   以中心点画圆： alt + 拖拽 再利用变换选区功能即可实现圆的选中 效果如图所示： 再使用自由变换，即可放大，缩小球的大小: ctrl + T 阴影部分的处理： 1）去其他球那里选择个椭圆形选区 2）选择编辑-填充 3）使用滤镜里
阅读更多...
Windows Server 2019 中文版、英文版下载 (updated Aug 2024)

Windows Server 2019 中文版、英文版下载 (updated Aug 2024)

Windows Server 2019 中文版、英文版下载 (updated Aug 2024) Windows Server 2019 Version 1809 请访问原文链接：https://sysin.org/blog/windows-server-2019/，查看最新版。原创作品，转载请保留出处。 本站将不定期发布官方原版风格月度更新 ISO。 Windows Server
阅读更多...
NLP-预训练模型-2019-NLU：RoBERTa【 优化版Bert】【丢掉NSP任务；Mask改为动态；放大数据集】

NLP-预训练模型-2019-NLU：RoBERTa【 优化版Bert】【丢掉NSP任务；Mask改为动态；放大数据集】

阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2