讲一下这场多校赛里面比较简单的三个题
HDU6045 Is Derek lying?
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6045
题意：有n道题，甲告诉乙，自己做对x道，对方做对了y道，而每道题有ABC三个选项。现在给出他们的卷子两个字符串，表示他们各自每道题的答案，现在请你通过这两个字符串判断甲是否说谎了。
思路：这道题一开始并没有想出来，过了很久才想出来，其实仔细想一下，如果甲没有撒谎，那么甲和乙对于一道题给出同样答案个数应该在一个区间内才对。上界是n-max(x,y)+min(x,y),下界应该是max（x+y-n，0）。
下界比较好理解，比如5个问题，x=3，y=3，那么他们肯定得答对至少相同的一道题，才可以满足。
对于上界可能比较难想，我们假设x<y,如果甲做的题目乙都做对了，但是乙没有做对的题目，加同样也没有作对而且答案还和乙一样，这是不是就是甲和乙相同答案最大的情况，把这段话转换成代码不就是n-max(x,y)+min(x,y)。我们只要确定甲乙两个的相同答案数在这个区间内说明甲没有说谎，否则就是说谎了。
代码：
//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=;
using namespace std;
typedef long long LL;
int main() {
ios::sync_with_stdio(false);cin.tie();
int T,n,x,y;
char q1[N],q2[N];
cin>>T;
while(T--){
cin>>n>>x>>y;
cin>>q1>>q2;
int ct=;
for(int i=;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 ;
}
HDU6047 Maximum Sequence
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6047
题意：现在有两个数组a，b。a是数组里面有一些数，但是需要处理一个c数组c[i]=a[i]-i，b是可供选择的左边界，用过以后就没有了。然后我们生成以后a数组的后n+1到2*n,我们在求第i个的时候可以选一个左边界，选择这个区间在c这个数组里面的最大值。求如果才能让a[n+1]到a[2*n]这n个数的和最大。
思路：肯定明白先用小的左边界，尽量可以包含最大值，我们我们对左边界排序，然后建立一个优先队列维护这个最大值。在当前边界大小小于堆顶定边界大小的时候，我们可以一直选这个最大值，大于或者等于的时候，把堆顶删除，然后再比较，直到枚举边界值小于堆顶边界值，然后对于新生成的元素我们把他门插入队。看代码吧。
代码：
//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=;
const long long mod=1e9+;
using namespace std;
typedef long long LL;
struct Node{
LL val,pos;
bool operator <(const Node &m) const{
if(val!=m.val) return val<m.val;
else{
return pos>=m.pos;
}
}
};
LL a[*N],b[N];
LL n;
priority_queue<Node>q;
int main() {
ios::sync_with_stdio(false);cin.tie();
while(cin>>n){
while(!q.empty()) q.pop();
for(int i=;i<=n;i++){
cin>>a[i];
q.push((Node){a[i]-i,i});
}
for(int i=;i<=n;i++) cin>>b[i]; sort(b+,b+n+);
int cur=;
for(LL i=n+;i<=*n;i++){
Node t=q.top();
while(b[cur]>t.pos){
q.pop();
t=q.top();
}
t=q.top();
a[i]=t.val;
q.push((Node){a[i]-i,i});
cur++;
}
LL sum=;
for(int i=n+;i<=*n;i++) sum=(sum+a[i])%mod;
cout<<sum<<endl; }
return ;
}
HDU6055 Regular polygon
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6055
题意：给出平面上一些整数坐标的点，问可以形成多少个不同的正多边形。
思路：首先明确一点，官方题解里面也写出来了，整数点形成正多边形只有正方形（比赛的时候就是一直在证明这个搞了好久，早知道应该大胆猜想）。知道这个以后就很简单，枚举两个点直接可以有公式可以算出另外两个点，注意根据这两个点向量方向，计算出的两对不同的点。比如我枚举x,y会算出a，b，但是枚举y，x就会算出c，d两个点，这两对点分布在x，y这个条线的两侧。我们现在只要判断算出来的两个点是否存在，题解用的是map，我用的直接用一个矩阵来记录，但是需要把这个题移到第一象限，这样所有的点才是都是正的，这样对于点查询复杂度就是O（1），速度比较快。
代码:
//Author:xiaowuga
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <bitset>
#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=+;
using namespace std;
int n;
int pic[][];
pair<int,int>s[N];
int main() {
while(cin>>n){
long long ct=;
mem(pic,);
for(int i=;i<n;i++){
cin>>s[i].first>>s[i].second;
pic[s[i].first+][s[i].second+]=;
}
for(int i=;i<n;i++)
for(int j=;j<n;j++){
if(i==j) continue;
pair<int,int>t1,t2;
int f1=,f2=;
t1.first=s[i].second-s[j].second+s[i].first;
t1.second=s[j].first-s[i].first+s[i].second;
if(pic[t1.first+][t1.second+]==) f1=;
t2.first=s[i].second-s[j].second+s[j].first;
t2.second=s[j].first-s[i].first+s[j].second;
if(pic[t2.first+][t2.second+]==) f2=;
if(f1&&f2) {
ct++;
}
}
cout<<ct/<<endl;
}
return ;
}