【ZZULIOJ】ZZULI-2019年3月份月赛（个人赛）_zzuli二元组

A.异或运算的基础题，但是很多人排序就过啦~~~

题解：

首先，变量元素对所有元素进行异或操作，得到的结果肯定是an^am。也就说通过异或操作以后，结果中保存了an和am的特征。由于am和an不同，am^an的结果肯定是大于等于1。am和an不同，那么am^an中为1的某一个bit肯定是am或者an中某一个的特征。

   然后，定义两个值num1，num2，分别用来计算an、am，选择am^an中的某一个bit作为特征位，假设是第K位是特征位，再次对元素进行遍历，如果元素的第K位是1，这个元素可能是am或者an，那么将当前元素与num1进行异或操作，如果元素的第K为不为0，那么这个元素则可能是另一个值，那么将当前元素与num2进行异或操作。这样遍历完所有元素，因为大部分数据成对出现，根据异或运算的特征，num1，num2就分别保存了两个不同的值。
 

#include<bits/stdc++.h>
using namespace std;
#define getbit(x,y)   ((x) >> (y)&1)//取出x的第y位 
int a[40],b[40];
int main()
{
	int n,k;
	cin>>n>>k;
	if(k==1)//一个特殊数，直接异或即可 
	{
		long long int ans,temp;
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&temp);
			if(i==0)
			{
				ans=temp;
			}
			else
			{
				ans^=temp;
			}
		}
		cout<<ans<<endl;
	}
	else
	{
		long long int ans,temp;
		for(int i=0;i<n;i++)//两个特殊数的时候，把每个数化成二进制， 第y位为1的时候，与a[]异或，否则与b[]异或 
		{
			scanf("%lld",&temp);
			for(int j=0;j<31;j++)
			{
				if(getbit(temp,j))
				{
					a[j]^=temp;
				}
				else
				{
					b[j]^=temp;
				}
			}
			if(i==0)
			{
				ans=temp;
			}
			else
			{
				ans^=temp;
			}
		}
		for(int j=0;j<31;j++)
		{
			if(getbit(ans,j))
			{
				cout<<min(a[j],b[j])<<' '<<max(a[j],b[j])<<endl;//从小到大输出 
				break;
			}
		}
	}
	return 0;
} 

B.签到题

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a;
    cin>>a;
    int g=0,s=0,b=0;
    b=a/10;
    s=a%10/5;
    g=a%10%5;
    cout<<b<<' '<<s<<' '<<g<<endl;
    return 0;
}

I.签到题

#include<bits/stdc++.h>
using namespace std;
long long int a[1000000+10];
int main()
{
    long long int k;
    cin>>k;
    a[1]=1;
    a[2]=1;
    for(int i=3;i<=1000000;i++)
    {
        a[i]=(a[i-2]*a[i-2]+a[i-1]*(i-1))%i;
    }
    cout<<a[k]<<endl;
    return 0;
}

G.统计字符出现的个数，相除后最小的记为答案。

#include<bits/stdc++.h>
using namespace std;
char s[10000+10];
char p[100];
int a[30],b[30];
int main()
{
    cin>>s>>p;
    int slen=strlen(s);
    for(int i=0;i<slen;i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            a[s[i]-'a']++;
        }
        if(s[i]>='A'&&s[i]<='Z')
        {
            a[s[i]-'A']++;
        }
    }
    int plen=strlen(p);
    for(int i=0;i<plen;i++)
    {
        if(p[i]>='a'&&p[i]<='z')
        {
            b[p[i]-'a']++;
        }
        if(p[i]>='A'&&p[i]<='Z')
        {
            b[p[i]-'A']++;
        }
    }
    int ans=99999;
     
    for(int i=0;i<26;i++)
    {
        if(b[i]!=0&&a[i]/b[i]<ans)
        {
            ans=a[i]/b[i];
        }
    }
    cout<<ans<<endl;     
    return 0;
}

H.最短路，注意重边，无向图。

djk的解法

/*
时间复杂度：O(n2)点的数量
*/
  
#include<bits/stdc++.h>
using namespace std;
#define MAX 3000
#define inf 2147483647
  
long long int d[MAX];//结点i的路径长度为d[i]
long long int v[MAX];//标记是否使用过该点
long long int w[MAX][MAX];//记录两点之间的花费 
long long int start=0,n,m,en;//起始点begin 点n表示点的数量 m表示边的数量
long long int fa[MAX];//维护父亲结点，用来找路径 
void init()//初始化
{
    for(int i=1;i<=n;i++)//把起点之外的点的距离设为inf，起点的距离设为0 
    {
        d[i]=(i==start ? 0:inf);
    }   
    memset(v,0,sizeof(v));//全部为未使用    0：未使用  1：使用
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            w[i][j]=inf;
}
void Dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        int pos,Min=inf;
        for(int j=1;j<=n;j++)//未标记的结点中，结点d[j]值最小的点 pos  
        {
            if(!v[j]&&d[j]<=Min)
            {
                Min=d[j];
                pos=j;
            }
        }
        v[pos]=1;//标记最小结点 pos
        for(int j=1;j<=n;j++)//对于从pos出发的所有边（pos,j）,更新 d[j]=min(d[j],d[pos]+w[pos][j])
        {
            //d[j]=min(d[j],d[pos]+w[pos][j]);
            if(d[j]>d[pos]+w[pos][j])
            {
                d[j]=d[pos]+w[pos][j];
                fa[j]=pos;
            } 
             
        }
    }
     
}
  
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&start,&en);
    init();
    for(int i=0;i<m;i++)
    {
        long long int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        //无向图 
        if(w[a][b]>c)
        {
            w[a][b]=c;
            w[b][a]=c;
        }   
    }
     
    Dijkstra();
    printf("%lld\n",d[en]);
    return 0;
}