小牧又偷懶了，最近兩天發生了很多事，小牧徹底變單身，不回頭，一切向ICPC看起，生活還要繼續，即使全世界都不在意你，你也要自強不息，當你變得優秀的時候這些都是你的故事，生活還要繼續，我還要我的金牌而努力，
今天呢補一下之前的div2
通天路
A題
題意：k次詢問，每次給你一個數n，然后給你n個數表示木板長度（寬度默認為1），求這些木板所能夠拼湊的最大正方形，輸出邊長
思路：將n個數排序，從大到小，記錄木棍的根數，當根數大于當前位置木棍長度時，最大正方形的邊長是根數減一，
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <string> 5 #include <algorithm> 6 7 using namespace std; 8 typedef long long ll; 9 int main() 10 { 11 int k; 12 cin >> k; 13 while(k--) 14 { 15 int n; 16 cin >> n; 17 int a[1010]; 18 for(int i=1;i<=n;i++) 19 { 20 cin >> a[i]; 21 } 22 sort(a+1,a+n+1); 23 if(a[n]==a[1]) 24 { 25 cout << a[n]<<endl; 26 continue; 27 } 28 int num =0,i=n; 29 while(a[i]>num&&i>0) 30 { 31 i--; 32 num++; 33 } 34 cout << num <<endl; 35 } 36 return 0; 37 }View Code
B1題
題意：給你兩個長度為n的字串，只能交換一次（且只能是從這串到另一個串交換），如果經過轉換可以得到兩個一樣的字串，則輸出YES否則輸出NO
思路：暴力列舉兩個串，找到兩個串對應不一樣的點，記錄點數，（且一定要是是s[i]!=t[i]&&s[j]==s[i]&&t[j]==t[i]）
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <cstdio> 5 #include <algorithm> 6 #include <map> 7 8 using namespace std; 9 typedef long long ll; 10 map<char,int>mp,q; 11 int main() 12 { 13 int k; 14 cin >> k; 15 while(k--) 16 { 17 int n; 18 cin >> n; 19 string s,t; 20 cin >> s; 21 cin >> t; 22 char a=0,b=0; 23 int num =0; 24 int flag = 0; 25 for(int i=0;i<n;i++) 26 { 27 if(s[i]!=t[i]) 28 { 29 num++; 30 if(a==0&&b==0) 31 { 32 a=s[i]; 33 b=t[i]; 34 continue; 35 } 36 else{ 37 if(a==s[i]&&b==t[i])flag=1; 38 //cout <<a <<s[i]<<b<<t[i]<<endl; 39 } 40 } 41 } 42 if(num==2&&flag==1) 43 { 44 cout<<"Yes"<<endl; 45 } 46 else{ 47 cout <<"No"<<endl; 48 } 49 } 50 return 0; 51 }View Code
B2題
題意：給你兩個長度為n的兩個串，最多可以經過2n次交換（不能相同串交換），如果經過變換可以得兩個相同的字串，則輸出yes和交換的次序對，否則輸出NO
思路：遍歷字串，每個位置的s,t兩串有三種情況：1.兩個相等，則直接跳過；2.兩不相等，但可以在(當前位置往后)找到與s[i]相等的s[k],則交換s[k]和t[i],并將選擇對存起來；
3.兩不相等，但可以在(當前位置往后)找到與s[i]相等的t[k],則交換s[i]和t[i],在交換s[i]和t[k],并將選擇對存起來；
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <string> 7 #include <map> 8 #include <queue> 9 using namespace std; 10 typedef long long ll; 11 map<char,int>mp; 12 vector<pair<int,int>>v; 13 14 int main() 15 { 16 int k; 17 cin >> k; 18 while(k--) 19 { 20 v.clear(); 21 int p; 22 cin >> p; 23 string s,ss; 24 cin >> s >> ss; 25 for(int i=0;i<p;i++) 26 { 27 for(int k=i+1;k<p;k++) 28 { 29 if(s[i]==ss[i])break; 30 if(s[k]==s[i]) 31 { 32 swap(ss[i],s[k]); 33 v.push_back({k,i}); 34 } 35 else if(ss[k]==s[i]) 36 { 37 swap(ss[i],ss[k]); 38 v.push_back({i,i}); 39 v.push_back({i,k}); 40 } 41 } 42 } 43 if(ss==s){ 44 //cout << s<<endl; 45 //cout << ss <<endl; 46 cout <<"Yes"<<endl; 47 cout <<v.size()<<endl; 48 for(auto vp: v) 49 { 50 cout << vp.first+1<<" "<<vp.second+1<<endl; 51 } 52 } 53 else{ 54 cout <<"No"<<endl; 55 } 56 } 57 }View Code
C題
題意：一個長度為n的彩帶（含有n個小正方形），對于任意n%|i-j|==0的話，第i個正方形和第J個正方形顏色相同，要求輸出最多的顏色數量
思路：就是n約數嘛，分三種情況：1.當n是素數時，最多就有n種顏色；2.當n的質因數只有一個時，就是n = pow(x,y)[x是n的唯一質因數，y是任意次方]，這個時候顏色最多有n的唯一質因數個3.就是n不止一個質因數，那就只能是一種顏色，因為這些質因數就是顏色相同的不同跨度，但他們有一個共同的倍數，都會過一個點【1，n】因此顏色都會是一樣的，
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstdio> 7 #include <vector> 8 9 using namespace std; 10 typedef long long ll; 11 12 int main() 13 { 14 ll n; 15 cin >> n; 16 for(int i=2;i<=sqrt(n);i++) 17 { 18 if(n%i==0) 19 { 20 while(n%i==0) 21 { 22 n/=i; 23 } 24 if(n>1) 25 { 26 cout <<1<<endl; 27 return 0; 28 } 29 else{ 30 cout << i<<endl; 31 return 0; 32 } 33 } 34 } 35 cout << n << endl; 36 return 0; 37 }View Code
再多的不舍，你也不會回來，也許你永遠都不會看我的博客，你也許從未在意我的博客，也許那句話是對的，你認真你就輸了，我來來回回說放下，搞了好多次，但我一次次回頭，一次次回來找你，你的冷淡，你的不理不睬，你沒有錯，錯只是我走出來的太慢了，今天之后，我不會再去找你，再見了，我的幻想，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127157.html
標籤：其他