专栏首页饶文津的专栏「2017 Multi-University Training Contest 2」2017多校训练2

「2017 Multi-University Training Contest 2」2017多校训练2

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 %d\n",++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]的值。

#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("%lld\n",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("%d\n",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

代码:

#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: %lld\n",++cas,ans);
	}
	return 0;
}

1008 To my boyfriend(子矩阵颜色数期望)

HDU6052-To my boyfriend

题意:

给你一个n行m列的矩阵,随机选一个子矩阵,求它不同数字的个数的期望。

代码:

#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("%.9f\n", num/((n+1)*n/2*(m+1)*m/2));//除以总子矩阵数
    }
    return 0;
}

1009 TrickGCD(莫比乌斯函数)

HDU6053-TrickGCD

代码:

#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: %lld\n",++cas,ans);
    }
    return 0;
}

1011 Regular polygon(正多边形计数)

HDU6055-Regular polygon

题意: 500个格点(坐标绝对值100以内),问有多少个正多边形。 题解: 只可能是正方形,枚举两个点,然后计算出另外两个点坐标,判断是否存在。

#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("%d\n",ans/4);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CodeForces 620D】Professor GukiZ and Two Arrays

    两个数列,一个有n个数,另一个有m个数,让你最多交换两次两个数列的数,使得两个数列和的差的绝对值最小,求这个差的绝对值、最少交换次数、交换数对

    饶文津
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 【HDU 5438】Ponds

    存边的时候,要头尾都存这个边。用dfs或者队列删点,再用并查集或者dfs确定联通块,然后统计联通块的点数,最后累加。

    饶文津
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • BZOJ4300: 绝世好题(dp)

    给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。

    attack
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事
  • 【C语言笔记】函数参数压栈的顺序?

    按照日常习惯来看,C语言的函数参数压栈顺序是从左到右吧?但是事实却是相反的,C语言函数参数压栈顺序是从右到左的。下面看一个程序:

    正念君
  • 图论--拓扑排序--模板

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券