講一下這場多校賽里面比較簡單的三個題

HDU6045 ?Is Derek lying?

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=6045

題意：有n道題，甲告訴乙，自己做對x道，對方做對了y道，而每道題有ABC三個選項。現(xiàn)在給出他們的卷子兩個字符串，表示他們各自每道題的答案，現(xiàn)在請你通過這兩個字符串判斷甲是否說謊了。

思路：這道題一開始并沒有想出來，過了很久才想出來，其實仔細(xì)想一下，如果甲沒有撒謊，那么甲和乙對于一道題給出同樣答案個數(shù)應(yīng)該在一個區(qū)間內(nèi)才對。上界是n-max(x,y)+min(x,y),下界應(yīng)該是max（x+y-n，0）。

下界比較好理解，比如5個問題，x=3，y=3，那么他們肯定得答對至少相同的一道題，才可以滿足。

對于上界可能比較難想，我們假設(shè)x<y,如果甲做的題目乙都做對了，但是乙沒有做對的題目，加同樣也沒有作對而且答案還和乙一樣，這是不是就是甲和乙相同答案最大的情況，把這段話轉(zhuǎn)換成代碼不就是n-max(x,y)+min(x,y)。我們只要確定甲乙兩個的相同答案數(shù)在這個區(qū)間內(nèi)說明甲沒有說謊，否則就是說謊了。

代碼：

//Author: xiaowuga #include <iostream> #include <algorithm> #include <set> #include <vector> #include <queue> #include <cmath> #include <cstring> #include <cstdio> #include <ctime> #include <map> #include <bitset> #include <cctype> #define maxx INT_MAX #define minn INT_MIN #define inf 0x3f3f3f3f #define mem(s,ch) memset(s,ch,sizeof(s)) #define da cout<<da<<endl #define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl; #define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl; const long long N=80000; using namespace std; typedef long long LL; int main() {ios::sync_with_stdio(false);cin.tie(0);int T,n,x,y;char q1[N],q2[N];cin>>T;while(T--){cin>>n>>x>>y;cin>>q1>>q2;int ct=0;for(int i=0;i<n;i++) if(q1[i]==q2[i]) ct++;int l=x+y-n;int r=n-max(x,y)+min(x,y);if(ct>=l&&ct<=r) cout<<"Not lying"<<endl;else cout<<"Lying"<<endl; }return 0; } View Code

HDU6047 ?Maximum Sequence

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6047

題意：現(xiàn)在有兩個數(shù)組a，b。a是數(shù)組里面有一些數(shù)，但是需要處理一個c數(shù)組c[i]=a[i]-i，b是可供選擇的左邊界，用過以后就沒有了。然后我們生成以后a數(shù)組的后n+1到2*n,我們在求第i個的時候可以選一個左邊界，選擇這個區(qū)間在c這個數(shù)組里面的最大值。求如果才能讓a[n+1]到a[2*n]這n個數(shù)的和最大。

思路：肯定明白先用小的左邊界，盡量可以包含最大值，我們我們對左邊界排序，然后建立一個優(yōu)先隊列維護(hù)這個最大值。在當(dāng)前邊界大小小于堆頂定邊界大小的時候，我們可以一直選這個最大值，大于或者等于的時候，把堆頂刪除，然后再比較，直到枚舉邊界值小于堆頂邊界值，然后對于新生成的元素我們把他門插入隊。看代碼吧。

代碼：

1 //Author: xiaowuga 2 #include <iostream> 3 #include <algorithm> 4 #include <set> 5 #include <vector> 6 #include <queue> 7 #include <cmath> 8 #include <cstring> 9 #include <cstdio> 10 #include <ctime> 11 #include <map> 12 #include <bitset> 13 #include <cctype> 14 #define maxx INT_MAX 15 #define minn INT_MIN 16 #define inf 0x3f3f3f3f 17 #define mem(s,ch) memset(s,ch,sizeof(s)) 18 #define da cout<<da<<endl 19 #define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl; 20 #define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl; 21 const long long N=250000; 22 const long long mod=1e9+7; 23 using namespace std; 24 typedef long long LL; 25 struct Node{ 26 LL val,pos; 27 bool operator <(const Node &m) const{ 28 if(val!=m.val) return val<m.val; 29 else{ 30 return pos>=m.pos; 31 } 32 } 33 }; 34 LL a[2*N],b[N]; 35 LL n; 36 priority_queue<Node>q; 37 int main() { 38 ios::sync_with_stdio(false);cin.tie(0); 39 while(cin>>n){ 40 while(!q.empty()) q.pop(); 41 for(int i=1;i<=n;i++){ 42 cin>>a[i]; 43 q.push((Node){a[i]-i,i}); 44 } 45 for(int i=1;i<=n;i++) cin>>b[i]; sort(b+1,b+n+1); 46 int cur=1; 47 for(LL i=n+1;i<=2*n;i++){ 48 Node t=q.top(); 49 while(b[cur]>t.pos){ 50 q.pop(); 51 t=q.top(); 52 } 53 t=q.top(); 54 a[i]=t.val; 55 q.push((Node){a[i]-i,i}); 56 cur++; 57 } 58 LL sum=0; 59 for(int i=n+1;i<=2*n;i++) sum=(sum+a[i])%mod; 60 cout<<sum<<endl; 61 62 } 63 return 0; 64 } View Code

?

HDU6055?Regular polygon

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6055

題意：給出平面上一些整數(shù)坐標(biāo)的點，問可以形成多少個不同的正多邊形。

思路：首先明確一點，官方題解里面也寫出來了，整數(shù)點形成正多邊形只有正方形（比賽的時候就是一直在證明這個搞了好久，早知道應(yīng)該大膽猜想）。知道這個以后就很簡單，枚舉兩個點直接可以有公式可以算出另外兩個點，注意根據(jù)這兩個點向量方向，計算出的兩對不同的點。比如我枚舉x,y會算出a，b，但是枚舉y，x就會算出c，d兩個點，這兩對點分布在x，y這個條線的兩側(cè)。我們現(xiàn)在只要判斷算出來的兩個點是否存在，題解用的是map，我用的直接用一個矩陣來記錄，但是需要把這個題移到第一象限，這樣所有的點才是都是正的，這樣對于點查詢復(fù)雜度就是O（1），速度比較快。

代碼:

1 //Author:xiaowuga 2 #include <iostream> 3 #include <algorithm> 4 #include <set> 5 #include <vector> 6 #include <queue> 7 #include <cmath> 8 #include <cstring> 9 #include <cstdio> 10 #include <ctime> 11 #include <map> 12 #include <bitset> 13 #define mem(s,ch) memset(s,ch,sizeof(s)) 14 #define da cout<<da<<endl 15 #define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl; 16 #define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl; 17 const long long N=500+10; 18 using namespace std; 19 int n; 20 int pic[1000][1000]; 21 pair<int,int>s[N]; 22 int main() { 23 while(cin>>n){ 24 long long ct=0; 25 mem(pic,0); 26 for(int i=0;i<n;i++){ 27 cin>>s[i].first>>s[i].second; 28 pic[s[i].first+300][s[i].second+300]=1; 29 } 30 for(int i=0;i<n;i++) 31 for(int j=0;j<n;j++){ 32 if(i==j) continue; 33 pair<int,int>t1,t2; 34 int f1=1,f2=1; 35 t1.first=s[i].second-s[j].second+s[i].first; 36 t1.second=s[j].first-s[i].first+s[i].second; 37 if(pic[t1.first+300][t1.second+300]==0) f1=0; 38 t2.first=s[i].second-s[j].second+s[j].first; 39 t2.second=s[j].first-s[i].first+s[j].second; 40 if(pic[t2.first+300][t2.second+300]==0) f2=0; 41 if(f1&&f2) { 42 ct++; 43 } 44 } 45 cout<<ct/4<<endl; 46 } 47 return 0; 48 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiaowuga/p/7261064.html

總結(jié)

以上是生活随笔為你收集整理的2017 Multi-University Training Contest - Team 2——HDU6045HDU6047HDU6055的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。