1001 Is Derek lying
题目链接 HDU6045 Is Derek lying?
#include <bits/stdc .h>
#define N 100001
using namespace std;
int t;
int n,x,y;
char s1[N],s2[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d%s%s",&n,&x,&y,s1,s2);
if(x<y)swap(x,y);
int dif=0,sam=0;
for(int i=0;i<n; i)if(s1[i]!=s2[i]) dif;else sam;
if(x-y>dif||y>sam&&dif-(y-sam)*2<x-y)puts("Lying");
else puts("Not lying");
}
return 0;
}1002 hash（哈希）
题目链接 HDU6046 hash
#include <bits/stdc .h>
#define N 1000
#define K 7
using namespace std;
#define LL long long
int t,cas;
char s[N 1][N 1];
map<unsigned LL,pair<int,int> >haxi;
inline unsigned sfr(unsigned h,unsigned x){
return h>>x;
}
int f(LL i,LL j){
LL w=i*1000000ll j;
int h=0;
for(int k=0;k<5; k){
h =(int)((w>>(8*k))&255);
h =(h<<10);
h^=sfr(h,6);
}
h =h<<3;
h^=sfr(h,11);
h =h<<15;
return sfr(h,27)&1;
}
int main(){
for(int i=1;i<=1000000;i =N-K)
for(int j=1;j<=1000000;j =N-K){
unsigned LL ss=13;
unsigned LL hx=0;
for(int k=0;k<K; k)
for(int g=0;g<K; g){
hx=hx*ss f(i k,j g);
ss*=13;
}
haxi[hx]=make_pair(i,j);
}
scanf("%d",&t);
int x=0,y=0;
while(t--){
for(int i=0;i<N; i)scanf("%s",s[i]);
bool fnd=false;
for(int i=0;i<N; i){
for(int j=0;j<N; j){
unsigned LL ss=13;
unsigned LL hx=0;
for(int k=0;k<K; k)
for(int g=0;g<K; g){
hx=hx*ss s[i k][j g]-'0';
ss*=13;
}
if(haxi.find(hx)!=haxi.end()){
fnd=true;
x=haxi[hx].first-i;
y=haxi[hx].second-j;
break;
}
}
if(fnd)break;
}
printf("Case #%d :%d %dn", cas,x,y);
}
return 0;
}1003 Maximum Sequence（贪心）
题目链接 HDU6047 Maximum Sequence
给定数组a[1..n]和b[1..n]，b[i]在[1~n]内。要得到a[n 1..2n]，每次选b数组的一个，令a[i]为j=b[k]到i-1位置中最大的a[j]-j。求a[n 1..2n]总和最大值。
每次b选最小的，这次的a[i]就能尽量大，而b[k]到i-1的位置中最大的a[j]-j，早晚要加到总和中，先选不会更差。
对a预处理为a[i]-i。b桶排序。剩下就是每次选出b[k]到i-1位置中最大值。a[i..n]中最大值可以用一个数组记录起来，即后缀最大值。然后a[n 1..i]最大值可以用一个变量维护。每次选两个区间的最大值作为当前a[i]的值。
代码语言：javascript复制#include <bits/stdc .h>
#define ll long long
#define N 250001
#define mem(a,b) memset(a,b,sizeof (a))
#define INF 0x3f3f3f3f
#define LL long long
const LL MOD=(1e9 7);
using namespace std;
int a[N],b[N];
int c[N];
int n;
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n; i){
scanf("%d",&a[i]);
a[i]-=i;
}
c[n]=a[n];
for(int i=n-1;i;--i)
c[i]=max(c[i 1],a[i]);
mem(b,0);
for(int i=1;i<=n; i){
int c;
scanf("%d",&c);
b[c];
}
LL ans=0;
int j=1;
int maxs=-INF;
for(int i=1;i<=n; i){
while(b[j]==0) j;
--b[j];
int now=max(c[j],maxs);
ans=(ans now)%MOD;
maxs=max(maxs,now-n-i);
}
printf("%lldn",ans);
}
return 0;
}1004 Puzzle（逆序对数）
题目链接 HDU6048 Puzzle
#include<bits/stdc .h>
using namespace std;
int t,n,m,p;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&p);
int tot=n*m-1, rev=0;
while(tot>p){
int num=(tot-1)/p 1;
tot-=num;
rev =num*(num-1)/2*(p-1);
}
puts(rev&1?"NO":"YES");
}
return 0;
}1005 Sdjpx Is Happy(区间dp)
HDU6049-Sdjpx Is Happy
#include <bits/stdc .h>
#define N 3001
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int t,n;
int mi[N][N],ma[N][N],f[N][N],r[N];
int a[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
mem(f,0);
for(int i=1;i<=n; i)
scanf("%d",a i);
for(int i=1;i<=n; i){
mi[i][i]=ma[i][i]=a[i];
r[i]=i;
f[i][i]=1;
for(int j=i 1;j<=n; j){
mi[i][j]=min(mi[i][j-1],a[j]);
ma[i][j]=max(ma[i][j-1],a[j]);
}
}
for(int l=2;l<=n; l){
for(int i=1;i<=n-l 1; i){
int j=i l-1;
if(ma[i][j]-mi[i][j]==l-1){
if(mi[i][r[i]]==mi[i][j])
f[i][j]=f[i][r[i]] f[r[i] 1][j];
else
f[i][j]=1;
r[i]=j;
}else{
f[i][j]=0;
}
}
}
int res=f[1][n];
for(int i=1;i<=n; i)
for(int j=i;j<=n; j)
if(f[i][j]&&(i==1||f[1][i-1]&&mi[1][i-1]==1)){
int jj=ma[i][j];
if(jj==n||ma[jj 1][n]==n&&f[jj 1][n])
for(int ii=jj; ii>j; --ii)
if(f[ii][jj]&&mi[ii][jj]==i)
res=max(res,f[1][i-1] f[j 1][ii-1] f[jj 1][n] 2);
}
printf("%dn",res);
}
return 0;
}1006 Funny Function(递推)
HDU6050-Funny Function
代码：
#include <bits/stdc .h>
#define mem(a,b) memset(a,b,sizeof (a))
using namespace std;
typedef long long ll;
const ll MOD=(1e9 7);
int t;
ll n,m;
ll qpow(ll a,ll b){
a%=MOD;
ll ans=1;
for(;b;b>>=1,a=a*a%MOD)
if(b&1)ans=ans*a%MOD;
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>t;
while(t--){
cin>>n>>m;
ll ans=(qpow(2,n)-1 MOD)%MOD;
ans=qpow(ans,m-1)*2%MOD;
if(m==1){
puts("1");
continue;
}
ll chuyi3=qpow(3,MOD-2)%MOD;
if(n&1){
cout<<(ans 1)*chuyi3%MOD<<endl;
}else{
cout<<ans*chuyi3%MOD<<endl;
}
}
return 0;
}1007 If the starlight never fade(原根,gcd求和)
HDU6051-If the starlight never fade
代码：
代码语言：javascript复制#include <bits/stdc .h>
#define ll long long
const ll M=1e9 7;
using namespace std;
int t,cas;
ll p,m;
ll phi(int x){
ll res=x;
for(int i=2;i*i<=x; i)
if(x%i==0){
res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&m,&p);
ll ans=M-p*(p-1)/2%M;
/*for(ll i=1;i<p; i){
ans =__gcd(i,p-1)*i;
ans%=M;
}*/
--p;
for(int i=1;i*i<=p; i)
if(p%i==0){
int j=p/i;
ans =(1LL*j*phi(j) (j==1))/2%M*i*i%M;
if(i!=j)
ans =(1LL*i*phi(i) (i==1))/2%M*j*j%M;
ans%=M;
}
ans=ans*m%M;
printf("Case #%d: %lldn", cas,ans);
}
return 0;
}1008 To my boyfriend(子矩阵颜色数期望)
HDU6052-To my boyfriend
题意：
给你一个n行m列的矩阵，随机选一个子矩阵，求它不同数字的个数的期望。
代码：
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
struct Grid{
int c,x,y;
}g[10001];
bool cmp(const Grid &a,const Grid &b){
if(a.c==b.c){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
return a.c<b.c;
}
int cnt;
int t,n,m;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
cnt=0;
for(int i=1;i<=n; i)
for(int j=1;j<=m; j){
int c;
scanf("%d",&c);
g[cnt ]=(Grid){c,i,j};
}
sort(g,g cnt,cmp);
double num=0;
for(int c=0;c<cnt; c){//第c个格子
int left=1,right=m;//左上角的左边界，右下角的右边界
for(int up=g[c].x,t=c-1;up;--up){//上边界，即左上角的所在行
for(;t>=0&&g[t].x==up&&g[t].c==g[c].c;--t){//往前枚举第up行的同色格子
if(g[t].y>g[c].y)
right=min(right,g[t].y-1);
else
left=max(left,g[t].y 1);
}
if(up==g[c].x)right=m;//如果是同一行，右边界为m
num =(g[c].y-left 1)*(right-g[c].y 1)*(n-g[c].x 1);//累加贡献的矩阵数
}
}
printf("%.9fn", num/((n 1)*n/2*(m 1)*m/2));//除以总子矩阵数
}
return 0;
}1009 TrickGCD(莫比乌斯函数)
HDU6053-TrickGCD
代码：
代码语言：javascript复制#include <bits/stdc .h>
#define N 100001
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const ll MOD=1e9 7;
int mu[N];
int pr[N],cnt;
bool isp[N];
void init(){
mem(isp,true);
for(int i=2;i<N; i){
if(isp[i]){
mu[i]=-1;
pr[cnt ]=i;
}
for(int j=0;j<cnt&&pr[j]*i<N; j){
isp[i*pr[j]]=false;
if(i%pr[j]==0)break;
mu[i*pr[j]]=-mu[i];
}
}
}
ll qpow(ll x,int b){
ll ans=1;
for(;b;x=x*x%MOD,b>>=1)if(b&1)ans=ans*x%MOD;
return ans;
}
int t,cas,n,m;
int num[N];
int main(){
init();
scanf("%d",&t);
while(t--){
scanf("%d",&n);
mem(num,0);
for(int i=0;i<n; i){
int x;
scanf("%d",&x);
m=i?min(m,x):x;
num[x];
}
for(int i=1;i<N; i)
num[i] =num[i-1];
ll ans=0;
for(int g=2;g<=m; g){
ll tmp=1;
for(int i=g,l=1;i<N;i =g, l){
int c=num[min(i g,N)-1]-num[i-1];
tmp=tmp*qpow(l,c)%MOD;
}
ans=((ans-tmp*mu[g])%MOD MOD)%MOD;
}
printf("Case #%d: %lldn", cas,ans);
}
return 0;
}1011 Regular polygon(正多边形计数)
HDU6055-Regular polygon
题意： 500个格点(坐标绝对值100以内)，问有多少个正多边形。 题解： 只可能是正方形，枚举两个点，然后计算出另外两个点坐标，判断是否存在。
代码语言：javascript复制#include <bits/stdc .h>
#define N 501
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct P{
int x,y;
}p[N];
int n;
bool b[N][N];
bool ck(int x,int y){
return x>=0&&x<N&&y>=0&&y<N&&b[x][y];
}
int main(){
while(~scanf("%d",&n)){
mem(b,0);
for(int i=1;i<=n; i){
int x,y;
scanf("%d%d",&x,&y);
x =100,y =100;
b[x][y]=1;p[i]=(P){x,y};
}
int ans=0;
for(int i=1;i<n; i)
for(int j=i 1;j<=n; j){
int dx=p[i].x-p[j].x,dy=p[i].y-p[j].y;
for(int k=-1;k<2;k =2){
int cx=p[i].x k*dy,cy=p[i].y-k*dx;
int nx=p[j].x k*dy,ny=p[j].y-k*dx;
if(ck(cx,cy)&&ck(nx,ny))ans ;
}
}
printf("%dn",ans/4);
}
return 0;
}
