[ICPC2024 Xi‘an I] ICPC2024 邀請賽西安站(7/8/13)

心得

[ICPC2024 Xi'an I] ICPC2024 邀請賽西安站重現賽 - 比賽詳情 - 洛谷

7表示賽時ac了7個,8表示含補題總共ac數,13表示題目總數

題目

M.?Chained Lights

打表,發現只有k=1是YES

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10;
int t,n,k,fac[N],sum[N],light[N];
void press(int x)
{light[x]^=1;for (int y=x+x;y<=n;y+=x) press(y);
}
int main(){sci(t);while(t--){sci(n),sci(k);puts(k==1?"YES":"NO");}return 0;
}

J. Triangle

數三角形,手玩發現一些規律,

比如:n=3,m=9實際是15,然后發現和gcd有關

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10;
int a,b;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);
}
int main(){sci(a),sci(b);// if(a==b){//     printf("%lld\n",1ll*a*(a+1)/2);// }// else{ll v=gcd(a,b);ptlle((1ll*a*b-1ll*v*(a/v)*(b/v))/2+1ll*((a/v)*(b/v)+1)/2*v);//}return 0;
}
/*
3 9 = 15
*/

D. Make Them Straight

枚舉k,根據ai-i*k確定能在同一個序列里的子序列,子序列里的是不改的

首項得是正的,后面i*k>1e6說明一定要改

剪枝一下復雜度是可接受的O(klogn)

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10;
int n,a[N],b[N];
map<ll,ll>mp;
ll sum,ans;
int main(){sci(n);rep(i,0,n-1)sci(a[i]);rep(i,0,n-1){sci(b[i]);sum+=b[i];}ans=sum;rep(k,0,1000000){mp.clear();ll res=0;rep(i,0,n-1){ll v=a[i]-1ll*i*k;if(1ll*i*k>1000000)break;if(v<0)continue;mp[v]+=b[i];res=max(res,mp[v]);//if(mp[v]==9)printf("i:%d v:%lld mp:%lld\n",i,v,mp[v]);}ans=min(ans,sum-res);}ptlle(ans);return 0;
}
/*
3 9 = 15
*/

L. Rubbish Sorting

二進制子集枚舉一下,大概sosdp的思想,因為|s|<=5

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,M=2e7+10,INF=0x3f3f3f3f;
int q,n,op,x,y,bs[8];
char s[N];
int val[M],now=INF;
int main(){memset(val,INF,sizeof val);bs[0]=1;rep(i,1,6)bs[i]=bs[i-1]*28;sci(q);while(q--){sci(op);scanf("%s",s);n=strlen(s);if(op==1){sci(y);int w=0;rep(i,0,n-1){int v=s[i]-'a'+1;w+=v*bs[i];}val[w]=min(val[w],y);now=min(now,y);rep(p,1,n){int up=(1<<p)-1;rep(i,0,up-1){int w=0;rep(j,0,p-1){int z=i>>j&1,v=0;if(z)v=27;else v=(s[j]-'a'+1);w+=v*bs[j];}val[w]=min(val[w],y);}}}else{int w=0;rep(i,0,n-1){int v=s[i]-'a'+1;w+=v*bs[i];}if(val[w]!=INF){pte(val[w]);continue;}vector<int>mn(n+1,INF);mn[n]=now;rep(p,1,n){int up=(1<<p)-1;rep(i,0,up-1){int w=0,tot=0;rep(j,0,p-1){int z=i>>j&1,v=0;if(z)v=27,tot++;else v=(s[j]-'a'+1);w+=v*bs[j];}mn[tot+n-p]=min(mn[tot+n-p],val[w]);}}rep(i,0,n){if(mn[i]!=INF){//printf("i:%d mn:%d\n",i,mn[i]);pte(mn[i]);break;}}}}return 0;
}
/*
3 9 = 15
*/

B. Turn Off The Lights(構造)

最終一定是和某一列完全相同/完全相反的,

不妨和第i列完全相同,全是01011,那么再把這三列的1按列取消掉就可以了

所以枚舉和哪列相同,bitset加速統計,復雜度O(n^3/64)

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e3+10;
int n,k,a[N][N],sum[N];
bitset<1005>b[2][N];
bool flip[N];
bool ck(int i){int sum=0;rep(j,1,n){if(j==i)continue;int s1=(b[1][i]^b[0][j]).count(),s2=(b[0][i]^b[0][j]).count();if(s1<s2)flip[j]=1;else flip[j]=0;sum+=min(s1,s2);}return sum<=k;
}
void out(int i){//printf("i:%d\n",i);vector<P>ans;rep(j,1,n){if(j==i)continue;if(flip[j])ans.pb(P(j,0));rep(x,1,n){if(flip[j]){if(a[j][x]!=(a[i][x]^1))ans.pb(P(j,x));}else{if(a[j][x]!=a[i][x])ans.pb(P(j,x));}}}rep(x,1,n){if(a[i][x])ans.pb(P(0,x));}pte(SZ(ans));for(auto x:ans){printf("%d %d\n",x.fi,x.se);}
}
int main(){sci(n),sci(k);rep(i,1,n){rep(j,1,n){sci(a[i][j]);if(a[i][j])b[0][i].set(j);else b[1][i].set(j);}}rep(i,1,n){rep(x,0,1){if(ck(i)){out(i);return 0;}}}puts("-1");return 0;
}
/*
3 9 = 15
*/

F.?XOR Game(博弈)

先從大到小考慮ai=1的值,z是0的個數算最小的數

因為操作一次就可以獲得收益/ban掉對應收益,所以alice和bob會先搶這部分

剩下的局面,盡可能避免2的出現, 全是2的情況,誰先操作誰就輸了,

所以判一下剩下局面的奇偶性,奇數alice全取,偶數bob全ban

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e5+10;
int k,z,a[N],b[N],c;
int main(){sci(k);sci(z);rep(i,0,k-1){sci(a[i]);}per(i,k-1,0){if(a[i]==1){c++;if(c&1)b[i]=1;a[i]=0;}}per(i,k-1,0){if(a[i]&1)c++;}c+=(z&1);per(i,k-1,0){if(!a[i])continue;if(c&1)b[i]=1;}per(i,k-1,0){printf("%1d",b[i]);}puts("");return 0;
}
/*
3 9 = 15
*/

I.?Smart Quality Inspector(狀壓dp+區間dp)

避免后效性,肯定是從大到小考慮max值,

被前面的最大值覆蓋了的區間,再選最大值時就沒有貢獻了

dp[S]表示當前最大值已經覆蓋的狀態是S時的最大代價和

b[i][l][r]表示區間包含第i位且被[l,r]完整包含的區間的數量

新增一位時,往左往右拓展0的區域找到最左最右,這一段的b值對應的區間都是有貢獻的

復雜度O(n^5+n*2^n)

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=25,M=(1<<20)+5,INF=0x3f3f3f3f;
int n,k,m,l,r,a[N][N],b[N][N][N],dp[M];
void upd(int &x,int y){x=min(x,y);
}
int main(){sci(n),sci(k),sci(m);rep(i,1,m){sci(l),sci(r);a[l][r]++;}rep(i,1,n){rep(l,1,i){rep(r,i,n){rep(x,l,i){rep(y,i,r){b[i][l][r]+=a[x][y];}}}}}memset(dp,INF,sizeof dp);dp[0]=0;int up=(1<<n)-1;rep(i,0,up){vector<int>pre(n,-1),suf(n,n);int now=-1,bit=0;rep(j,0,n-1){int v=i>>j&1;if(v==1)now=j,bit++;else pre[j]=now+1;}now=n;per(j,n-1,0){int v=i>>j&1;if(v==1)now=j;else{suf[j]=now-1;int x=j+1,y=pre[j]+1,z=suf[j]+1;upd(dp[i|(1<<j)],dp[i]+b[x][y][z]*max(k-bit,0));}}}pte(dp[up]);return 0;
}

賽后補題

G.?The Last Cumulonimbus Cloud(拓撲排序好題)

任意非空子圖都有一個度不超過10的點=可以把度>10的點的貢獻都歸到這些不超過10的點上

拓撲排序每刪掉一個度數不足10的點就會多出一個不足10的點

最后圖可以化成一個聯通且每個點出度均不超過10的dag

u加的時候把貢獻推到u的下游

u算的時候上游已經推給過u,只需要再加上u的所有下游的貢獻

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/21578.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/21578.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/21578.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Mysql 技術實戰篇

命令行 導出 - -h localhost&#xff1a;指定MySQL服務器的主機地址為本地主機。如果MySQL服務器在其他主機上&#xff0c;請將localhost替換為相應的主機地址。 - -u username&#xff1a;指定連接MySQL服務器的用戶名。將username替換為您的有效用戶名。 - -p&#xff1a;提…

Makefile教程(附通用模板)

工程目錄 工程目錄如圖&#xff0c;build文件夾是編譯出來的 . ├── app │ ├── imx6ul.lds │ ├── main.c │ ├── makefile │ └── start.S ├── bsp │ ├── clk │ │ ├── bsp_clk.c │ │ └── bsp_clk.h │ ├── delay │…

軟考 系統架構設計師系列知識點之SOME/IP與DDS(1)

本文內容參考&#xff1a; 車載以太網 - SOME/IP簡介_someip-CSDN博客 https://zhuanlan.zhihu.com/p/369422441 什么是SOME/IP?_someip-CSDN博客 SOME/IP 詳解系列&#xff08;1&#xff09;—— 概述_some ip-CSDN博客 深入淺出SOME/IP協議&#xff1a;基本概念和原理-…

天童教育:停止內耗放松身心

如果一個人經常從自己身上找原因&#xff0c;經常攬下他人的過錯的責任&#xff0c;總是自我懷疑自我否定&#xff0c;認為自己不值得被愛。當被人誤解時會在心里悄悄附和&#xff0c;責怪自己。缺乏自信&#xff0c;沒辦法和他人有正常的交往&#xff0c;長期處于身心疲憊的狀…

Python與Python3的區別:深度剖析與全面解讀

Python與Python3的區別&#xff1a;深度剖析與全面解讀 在編程領域&#xff0c;Python和Python3是兩個常被提及的版本&#xff0c;它們之間既存在相似之處&#xff0c;又有著顯著的區別。本文將從四個方面、五個方面、六個方面和七個方面&#xff0c;深入剖析Python與Python3之…

OJ3376無盡的石頭問題

答案&#xff1a; #include<bits/stdc.h> using namespace std; const int N10e7; int fx(int n) {int sum0;while(n){sum(n%10);n/10;}return sum; } int main() {int t,n,x;cin>>t;while(t--){cin>>n;int count0;for(int i1;i<N;){if(in){cout<<…

在github上創建(上傳、關聯)自已的項目

目錄 創建一個github項目并進行開發。 1.github創建空項目 2. git clone 項目 3. 將項目關聯 創建一個github項目并進行開發。 1.github創建空項目 右邊的New 然后按步創建就行 2. git clone 項目 復制這個連接 然后在終端&#xff1a;git clone [剛才復制的連接] 3. 將…

解讀 Explainable Image Similarity Integrating Siamese Networks and Grad-CAM

給出論文&#xff08;Explainable Image Similarity Integrating Siamese Networks and Grad-CAM&#xff09;的內容解讀、代碼運行說明 論文鏈接&#xff1a;J. Imaging | Free Full-Text | Explainable Image Similarity: Integrating Siamese Networks and Grad-CAM (mdpi.c…

純網絡的系統能否定級備案?

很多單位想把網絡基礎設施進行定級備案和測評&#xff0c;但是不知道這樣可否&#xff1f; 目前湖北省是可以的。因為根據《定級指南》的術語解釋3.2對等級保護對象的定義是包括通信基礎設施的&#xff0c;也就是網絡基礎設施。其他地區目前有的地方可以有的地方不行&#xff…

2024年武漢東湖高新中級職稱報名時間是什么時候?

2024年武漢市東湖高新中級職稱上半年批次報名已經截止了&#xff0c;下半年東湖高新至少還有一次報名機會&#xff0c;所以各位東湖高新區評職稱的朋友們&#xff0c;不要錯過這次了。 2024年武漢東湖高新區中級職稱報名條件&#xff1a; 1.東湖高新區社保滿足1年&#xff0c;近…

進口不銹鋼氣動輸送泵-美國品牌

進口不銹鋼氣動輸送泵是一種利用壓縮空氣為動力&#xff0c;通過氣閥控制進行往復運動&#xff0c;將能量轉換為泵的動能&#xff0c;從而實現對液體或固體物料輸送的設備。以下是關于進口不銹鋼氣動輸送泵的詳細介紹&#xff1a; 一、產品特點 材質優良&#xff1a;主體部分…

seata源碼分析(03)_創建代理的過程

seata提供了ProxyUtil工具類為事務組件創建代理對象&#xff0c;在spring環境中&#xff0c;seata提供了GlobalTransactionScanner類和SeataAutoDataSourceProxyCreator為組件創建AOP代理&#xff0c;本文重點分析這兩個類。 ProxyUtil io.seata.integration.tx.api.util.Pro…

【中年危機】程序猿自救指南

中年危機&#xff0c;一個聽起來就充滿挑戰的詞匯&#xff0c;它不僅僅是一個年齡的標記&#xff0c;更是一個個人成長和職業發展的轉折點。 構架個人品牌&#xff1a; 學會打造IP個人品牌是職業生涯中的重要資產。在中年時期&#xff0c;你已經積累了豐富的經驗和知識&#x…

golang的http客戶端封裝

簡介 net/http 是 Go 語言標準庫的一部分&#xff0c;它提供了創建 HTTP 客戶端和服務器的能力。這個包通過簡化與 HTTP 協議的交互&#xff0c;讓開發者能夠方便地構建 HTTP 請求和響應&#xff0c;以及處理路由等任務。 本文以 net/http 包作為底層&#xff0c;封裝一個包含…

HTCC電路板是什么,有哪些主要應用領域

HTCC英文名稱是High-Temperature Co-Fired Ceramic&#xff0c;又稱高溫共燒多層陶瓷基板。因其具有導熱系數高、耐熱性好、熱膨脹系數小、機械強度高、絕緣性好、耐腐蝕等優勢&#xff0c;是保持高速增加的PCB線路板之一。 SPEA作為專業電路板測試設備方案服務商&#xff0c;公…

FY-SA-20237·8-WhyWeSpin

Translated from the Scientific American, July/August 2023 issue. Why We Spin (我們為什么旋轉) Primates may play with reality by twirling around 翻譯&#xff1a;靈長類動物有能力通過旋轉或旋轉運動來操縱或扭曲他們對現實的感知。 解釋&#xff1a; “Primates”…

Java生成指定長度驗證碼

生成指定長度驗證碼的簡單思路在Java中通常涉及以下幾個步驟&#xff1a; 1、定義字符池&#xff1a; 首先&#xff0c;需要定義一個包含所有可能字符的字符串&#xff0c;這個字符池通常包括數字(0-9)、大寫字母(A-Z)、小寫字母(a-z)。 例如&#xff1a; String chars "…

【開發心得】三步本地化部署llama3大模型

目錄 第一步&#xff1a;啟動ollama 第二步&#xff1a;啟動dify 第三步&#xff1a;配置模型&#xff08;截圖&#xff09; 最近llama3很火&#xff0c;本文追擊熱點&#xff0c;做一個本地化部署的嘗試&#xff0c;結果還成功了&#xff01; 當然也是站在別人的肩膀上&…

【運維項目經歷|027】PXE自動化部署與管理平臺

&#x1f341;博主簡介&#xff1a; &#x1f3c5;云計算領域優質創作者 &#x1f3c5;2022年CSDN新星計劃python賽道第一名 &#x1f3c5;2022年CSDN原力計劃優質作者 &#x1f3c5;阿里云ACE認證高級工程師 &#x1f3c5;阿里云開發者社區專…

Nginx企業級負載均衡:技術詳解系列(18)—— 作為上傳服務器

你好&#xff0c;我是趙興晨&#xff0c;97年文科程序員。 在上一期的技術分享中&#xff0c;我們探討了如何高效搭建Nginx下載服務器&#xff0c;并討論了長連接優化策略。那么今天&#xff0c;咱們進一步了解Nginx的另一面——作為上傳服務器的配置技巧。 作為上傳服務器&a…