2022杭电多校联赛第二场 题解
签到题
1002题 C to Python / C 到Python
题目大意
把 std::make_tuple(1,2) 变成 (1,2) 的形式。
考察内容
签到
分析
把 “std::make_tuple” 中的字符忽略即可。
#include<bits/stdc .h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6 10;
ll n,m,a[N];
string s;
string s0="std::make_tuple";
map<char,int> mp;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll len2=s0.size();
for(int i=0;i<len2;i ){
mp[s0[i]]=1;
}
int t; cin>>t;
while(t--){
cin>>s; ll len=s.size();
for(int i=0;i<len;i ){
if(mp[s[i]]!=1){
cout<<s[i];
}
}
cout<<endl;
}
return 0;
}
1007题 Snatch Groceries / 抢菜
题目大意
给定 n n n 个区间,按时间顺序,求区间重叠前有几个区间。端点重合也算重叠。
考察内容
排序
分析
按照区间左端点排序,然后暴力枚举即可。
#include<bits/stdc .h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6 10;
ll n,m;
struct node{
ll l,r;
}a[N];
bool cmp(node x,node y){
if(x.l!=y.l)return x.l<y.l;
return x.r>y.r;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i ){
cin>>a[i].l>>a[i].r;
}
sort(a 1,a n 1,cmp);
ll maxr=a[1].r;
ll ans=0;
for(int i=2;i<=n;i ){
if(a[i].l<=maxr){
break;
}
else{ // a[i].l>maxr
maxr=max(maxr,a[i].r);
ans ;
}
}
if(ans==n-1){
ans ;
}
cout<<ans<<endl;
}
return 0;
}
/*
1
3
1 10
10 20
15 16
*/
基本题
1012题 Luxury cruise ship / 豪华游轮
题目大意
用体积为7、31或365的物品装填容量为 n n n 的背包,求把背包装满最少需要多少个物品。不能装满输出-1。
考察内容
dp,背包,贪心
分析
n n n 较小,直接背包dp。
n n n 很大时,用365填充到一个较小的范围,再dp。
#include<bits/stdc .h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
ll n;
ll f[160005];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for(int i=0;i<=160000;i ){
f[i]=1e18 10;
}
f[0]=0;
for(int i=365;i<160000;i =365){
f[i]=f[i-365] 1;
}
for(int i=31;i<160000;i ){
f[i]=min(f[i],f[i-31] 1);
}
for(int i=7;i<160000;i ){
f[i]=min(f[i],f[i-7] 1);
}
int t; cin>>t;
while(t--){
cin>>n;
if(ny205==0){ // 每一份
cout<<n/365<<endl;
continue;
}
// ny205!=0时
ll ans=0;
if(n>79205){ // n很大
ans = (n-79205)/365; // 优先用365面值的硬币
n -= ans*365;
}
if(f[n]>1e17){
cout<<-1<<endl;
}
else{
cout<<f[n] ans<<endl;
}
}
return 0;
}
/*
输入:
1
79211
输出:
245
*/
1009题 ShuanQ / “栓Q”
题目大意
rsa加密算法中,给定私钥 p p p ,公钥 q q q ,密文 x x x,求解明文 a n s ans ans。若无法求解则输出 “ShuanQ” 。
其中 p , q , x , a n s p,q,x,ans p,q,x,ans 满足:
p × q ≡ 1 m o d M p×q≡1 \mod M p×q≡1modM ,其中 M M M 为质数且 M > p , M > q , M > x M>p, M>q, M>x M>p,M>q,M>x 。
a n s = x × q m o d M ans=x×q \mod M ans=x×qmodM
考察内容
质数,数学知识
分析
思路:先找出M,然后可以通过 a n s = x × q m o d M ans=x×q \mod M ans=x×qmodM 直接计算出明文。
已知 p × q m o d M = 1 p×q \mod M=1 p×qmodM=1
移项得,
( p × q − 1 ) m o d M = 0 (p×q-1) \mod M =0 (p×q−1)modM=0
从 1 1 1 到 p × q − 1 \sqrt{p×q-1} p×q−1 枚举因数 i i i ,质数的 ( p × q − 1 ) / i (p×q-1)/i (p×q−1)/i 即为一个合法的 M M M 。
#include<bits/stdc .h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
ll n,m;
bool isp(ll x){
if(x<=1)return 0;
for(int i=2;i<=sqrt(x);i ){
if(x%i==0)return 0;
}
return 1;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
ll p,q,x;
cin>>p>>q>>x; // 私钥,公钥,密文
ll m=max(p,q); m=max(m,x); m ;
ll ansm=-1;
ll pq1=p*q-1;
for(int i=1;i<=sqrt(pq1);i ){ // 枚举
if(pq1%i==0){
if(isp(pq1/i)){
ansm=pq1/i;
break;
}
}
}
if(ansm!=-1){
cout<<x*q%ansm<<endl;
}
else{
cout<<"shuanQ"<<endl;
}
}
return 0;
}
/*
1
1 1 1
1
2000000 2000000 2000000
1
1999999 1999999 1999999
*/
进阶题
1003题 Copy / 复制
题目大意
给定一个数组 a a a , q q q 次操作。初始答案 a n s = 0 ans=0 ans=0 。
操作一:选择一段区间 [ l , r ] ( 1 ≤ l , r ≤ n ) [l,r] (1 \le l,r \le n) [l,r](1≤l,r≤n) ,在 r r r 后面紧跟着复制一段一样的区间,复制后超过 n n n 的部分可以忽略。操作一的总数不超过20000次。
操作二:查询一个数字 a [ x ] a[x] a[x] ,令 a n s = a n s ⊕ a [ x ] ans=ans⊕a[x] ans=ans⊕a[x] 。
求异或和 a n s ans ans 。
考察内容
离线,dp,bitset优化,暴力
分析
方法一:
暴力模拟。
方法二(官方解法):
一个修改操作对后续的查询操作的影响:如果 x ≤ r x \leq r x≤r 就没影响,如果 x > r x>r x>r ,相当于查询 x − ( r − l 1 ) x-(r-l 1) x−(r−l 1) ,然后去掉修改操作。
因此可以离线,倒着处理所有修改操作,每个修改操作都让它之后的所有 x > r x>r x>r 的询问 x − = r − l 1 x -= r - l 1 x−=r−l 1 。
但是这么处理还是 O ( n 2 ) O(n^2) O(n2) 的。考虑到我们只要答案的异或和,就有,两个相同的查询可以抵消,因此同一位置至多只会查询一次。这样每个位置用 1 bit 的信息表示即可,也就是 bitset。
我们令 dp 第 i 位为 1 表示答案需要对 a [ i ] a[i] a[i] 异或。倒着遍历所有操作,如果是查询操作, d p [ x ] dp[x] dp[x] ^= 1 1 1 ,如果是修改操作,那么就让 r 1... n r 1 ... n r 1...n 这些比特右移 r − l 1 r-l 1 r−l 1,代码如下:
low = dp & (~bitset<N>(0) >> (N - r - 1));
high = dp & (~bitset<N>(0) << (r 1));
dp = low ^ (high >> (r 1 - l));
方法一完整代码:
#include<bits/stdc .h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5 5;
int n,m,q,a[N];
int main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t; cin>>t;
while(t--){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i ){
scanf("%d",&a[i]);
}
ll ans=0;
int op,l,r,x;
for(int i=1;i<=q;i ){
scanf("%d",&op);
if(op==1){ // 区间更新,区间后面接一段一样的
scanf("%d%d",&l,&r);
if(r==n)continue; // 一整段复制,无意义,直接跳过
int F=l;
int t1=r r-l 1;
if(t1<n){
for(int i=n;i>t1;i--){
a[i]=a[i-(r-l 1)];
}
}
for(int i=r 1;i<=min(t1,n);i ){
a[i]=a[F];
F ;
}
}
else{ // op==2,单点查询
scanf("%d",&x);
ans=ans^a[x];
}
}
printf("%lld\n",ans);
}
return 0;
}
方法二完整代码:
#include <bits/stdc .h>
using namespace std;
const int N = 100010;
int a[N];
bitset<N> dp, low, high;
array<int, 3> v[N];
void solve() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= q; i ) {
scanf("%d", &v[i][0]);
if (v[i][0] == 1) {
scanf("%d%d", &v[i][1], &v[i][2]);
} else {
scanf("%d", &v[i][1]);
}
}
dp = 0;
for (int i = q; i >= 1; i--) {
if (v[i][0] == 1) {
int l = v[i][1], r = v[i][2];
low = dp & (~bitset<N>(0) >> (N - r - 1));
high = dp & (~bitset<N>(0) << (r 1));
dp = low ^ (high >> (r 1 - l));
} else {
int x = v[i][1];
dp[x] = !dp[x];
}
}
int ans = 0;
for (int i = 1; i <= n; i ) {
if (dp[i]) {
ans ^= a[i];
}
}
printf("%d\n", ans);
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgehhhg
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01