A 配对
题意：给定两个数列，求出这两个数列第K大的和的最大值
解答：从大到小排列，因为要使得前K大尽可能的大
那么范围一定是在两个数组前K大的数里面进行选择
相当于这K对数字的最小值要最大
那么只需要两个里面按照大小关系两两配对即可
即最大的与最小的配对，第二大的和第二小的配对
最后输出最小值即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif int n,k;cin>>n>>k; vector<int> a(n),b(n); for(auto &i:a) cin>>i; for(auto &i:b) cin>>i; sort(ALL(a),greater<int>()); sort(ALL(b),greater<int>()); vector<int> res; for(int i=0;i<k;i++){ res.push_back(a[i]+b[k-1-i]); } sort(ALL(res)); cout<<res[0]<<endl; return 0; } |
C 汉诺塔
题意：给定一堆木板，要往柱子上面放，放在下面的木板一定要比放在上面的木板两条边严格大于，并且不可以旋转这个木板，问最少需要多少柱子
解答：用res来存下每一个柱子的情况，先sort一下所有的木板，每加入一个新的木板，就二分查找到res里面最小的木板且刚好满足题意的情况，并更新一下res即可
需要特别注意下还要输出一下每一个木板在哪里，在排序之前记录一下id
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; struct pii{ int first; int second; int id; inline bool operator <(const pii &a)const{ return first<a.first or first==a.first and second<a.second; } }; pii p[100010]; vector<pii> res; int ans[100010],t[100010]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif int n;cin>>n; for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second,p[i].id=i; sort(p,p+n); for(int i=0;i<n;i++){ auto pos=upper_bound(ALL(res),p[i],[](const pii &a,const pii &b){return !(a.first<b.first or a.first==b.first and a.second<b.second);}); pos=upper_bound(pos,res.end(),p[i],[](const pii &a,const pii &b){return a.second>b.second;}); //if(pos!=res.end()) cout<<pos->first<<" "<<pos->second<<endl; if(pos==res.end()){ res.push_back(p[i]); ans[i]=res.size(); } else { *pos=p[i]; ans[i]=pos-res.begin()+1; } } cout<<res.size()<<endl; for(int i=0;i<n;i++) { t[p[i].id]=ans[i]; } for(int i=0;i<n;i++){ cout<<t[i]<<" "; } cout<<endl; return 0; } |
D 重排列
题意：给定两个序列，你可以随意重新组合这两个序列，问有多少种序列可以满足对任意\( i \leq j\)有\(a_i \leq a_j\)，其中相同的元素视作不同
解答：对A序列从大到小遍历，因为大的才会影响后面的选择，然后每看到一个数字就看B序列里面有多少个是大于A序列里面的元素的，然后对res乘上元素个数减去前面的元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif int n;cin>>n; vector<ll> a(n),b(n); for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; sort(ALL(a)),sort(ALL(b)); ll now=0,res=1; for(int i=n-1;i>=0;i--){ int pos=n-(lower_bound(ALL(b),a[i])-b.begin()); res=res*(pos-now)%mod; now++; } cout<<res<<endl; return 0; } |
F 十字阵列
题意：扔炸弹，对x行和y列造成z点伤害，假设最后第i行第j列伤害是\( w_{ij} \)问最后\( \Sigma w_{ij}(i+j) \)的值是多少
解答：和翻转棋升级版很像，大概就是记录一下每一行出现多少次，每一列有多少伤害，注意这里第i行第j列的伤害只计算一次，需要减掉
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; ll a[2010],b[2010]; ll t[2010][2010]; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif ll n,m,h;scanf("%lld%lld%lld",&n,&m,&h); ll res=0; for(int i=0;i<h;i++){ ll x,y,z;scanf("%lld%lld%lld",&x,&y,&z); a[x]+=z;b[y]+=z; t[x][y]-=z; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ res=(res+(i+j)*((a[i]+b[j]+t[i][j])%mod))%mod; } } printf("%lld\n",res); return 0; } |
G 括号序列
题意：给一个括号序列，问最少删除多少个括号，可以使得括号匹配
解答：用类似于括号匹配的方法来进行操作，在匹配的时候判断一下能不能匹配（判断一下栈里面有没有东西），不能匹配就删掉这个就可以了，注意最后要加上不能匹配的左括号的数量（即栈的size）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
/************************************************************************* >>> Author: WindCry1 >>> Mail: lanceyu120@gmail.com >>> Website: https://windcry1.com >>> Date: 12/30/2019 11:03:37 PM *************************************************************************/ //#pragma GCC optimize(2) //#pragma GCC diagnostic error "-std=c++11" #include <cstring> #include <cmath> #include <cstdio> #include <cctype> #include <cstdlib> #include <ctime> #include <vector> #include <iostream> #include <string> #include <queue> #include <set> #include <map> #include <algorithm> #include <complex> #include <stack> #include <bitset> #include <iomanip> #include <list> #include <sstream> #include <fstream> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define endl '\n' #define ALL(x) x.begin(),x.end() #define MP(x,y) make_pair(x,y) #define ll long long #define ull unsigned long long #ifdef WindCry1 #define DEBUG(x) cout<<#x<<" : "<<x<<endl; #endif #define lowbit(x) x&(-x) #define ls u<<1 #define rs u<<1|1 using namespace std; template<typename T> inline T MIN(const T &a,const T &b) {return a<b?a:b;} template<typename T> inline T MAX(const T &a,const T &b) {return a>b?a:b;} template<typename T,typename ...Args> inline T MIN(const T &a,const T &b,Args ...args) {return MIN(MIN(a,b),args...);} template<typename T,typename ...Args> inline T MAX(const T &a,const T &b,Args ...args) {return MAX(MAX(a,b),args...);} typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<double,double> pdd; const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int dir[4][2]={-1,0,1,0,0,-1,0,1}; int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #ifdef WindCry1 freopen("C:/Users/LENOVO/Desktop/in.txt","r",stdin); #endif int T;cin>>T;while(T--){ stack<char> st; int res=0; int n;string s;cin>>n>>s; for(auto i:s){ if(i=='(') st.push(i); if(i==')') { if(!st.empty()) st.pop(); else res++; } } res+=st.size(); cout<<res<<endl; } return 0; } |
I 导航系统
题意：给定一棵树所对应的邻接矩阵，问这个邻接矩阵能否自洽，如果可以还需要输出最短的i-1条边
解答：最小生成树跑出来结果，然后Floyd运行出最小生成树对应的邻接矩阵观察是否相同即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<cctype> #include<ctime> #include<iostream> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<iomanip> #include<list> #include<bitset> #include<sstream> #include<fstream> #include<complex> #include<algorithm> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define ll long long using namespace std; const int INF = 0x3f3f3f3f; int b[600][600],c[600][600]; int f[600]; struct sut{ int x,y,m; }a[1000010]; int cmp(sut a,sut b){ return a.m<b.m; } int find(int x){ if(f[x]==x) return x; else return f[x]=find(f[x]); } int uni(int a,int b){ int t1,t2; t1=find(a); t2=find(b); if(t1!=t2){ f[t2]=t1; return 1; } return 0; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n; cin>>n; int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int t; cin>>t; b[i][j]=t; if(i!=j){ cnt++; a[cnt].x=i; a[cnt].y=j; a[cnt].m=t; } } } bool flag=0; sort(a+1,a+1+cnt,cmp); for(int i=1;i<=n;i++) f[i]=i; int sum=0,ans=0; vector<int> res; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i!=j) c[i][j]=INF; } } for(int i=1;i<=cnt;i++){ if(uni(a[i].x,a[i].y)){ sum++; res.push_back(a[i].m); c[a[i].x][a[i].y]=a[i].m; c[a[i].y][a[i].x]=a[i].m; } if(sum==n-1) break; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=min(c[i][j],c[i][k]+c[k][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(c[i][j]!=b[i][j]) flag=1; } } if(flag) cout<<"No"<<endl; else{ cout<<"Yes"<<endl; sort(res.begin(),res.end()); for(auto i:res)cout<<i<<endl; } return 0; } |
J 签到题
题意：给定一个三角形的三条边，问从三个顶点做出的三个外切圆半径
解答：二分一个外切圆半径，然后判断三角形里面能否成立即可，注意二分大小关系
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<cctype> #include<ctime> #include<iostream> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<iomanip> #include<list> #include<bitset> #include<sstream> #include<fstream> #include<complex> #include<algorithm> #if __cplusplus >= 201103L #include <unordered_map> #include <unordered_set> #endif #define ll long long using namespace std; const int INF = 0x3f3f3f3f; int b[600][600],c[600][600]; int f[600]; struct sut{ int x,y,m; }a[1000010]; int cmp(sut a,sut b){ return a.m<b.m; } int find(int x){ if(f[x]==x) return x; else return f[x]=find(f[x]); } int uni(int a,int b){ int t1,t2; t1=find(a); t2=find(b); if(t1!=t2){ f[t2]=t1; return 1; } return 0; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n; cin>>n; int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int t; cin>>t; b[i][j]=t; if(i!=j){ cnt++; a[cnt].x=i; a[cnt].y=j; a[cnt].m=t; } } } bool flag=0; sort(a+1,a+1+cnt,cmp); for(int i=1;i<=n;i++) f[i]=i; int sum=0,ans=0; vector<int> res; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i!=j) c[i][j]=INF; } } for(int i=1;i<=cnt;i++){ if(uni(a[i].x,a[i].y)){ sum++; res.push_back(a[i].m); c[a[i].x][a[i].y]=a[i].m; c[a[i].y][a[i].x]=a[i].m; } if(sum==n-1) break; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c[i][j]=min(c[i][j],c[i][k]+c[k][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(c[i][j]!=b[i][j]) flag=1; } } if(flag) cout<<"No"<<endl; else{ cout<<"Yes"<<endl; sort(res.begin(),res.end()); for(auto i:res)cout<<i<<endl; } return 0; } |
0 条评论