11-06 热身赛

自用笔记算法

周赛（四）

A/B

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
void exgcd(int a,int b,int &x,int &y)
{
    if( b== 0 )
    {
        x= 1;
        y= 0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int p,q,y=9973; 
		long long B,n;
		cin>>n>>B;
		exgcd(y,B,p,q);
		q*=n;
		q=(q%y+y)%y;
		cout<<q<<endl;
	}
}

思路

exgcd模版题。
(n=A%9973)等价为A=9973X+n。y=(A/B)%9973等价为A/B=9973Z+y
因为A不知道，所以要把A消掉。得到的方程整理即是9973(ZB-X) +By = n
求y。所以把(ZB-X)当成一个未知数就可以了，扩展欧几里德A掉。

注意事项

乍看和不定方程无关。但是经过最简单的数学化简后即可化成不定方程，带入exgcd模版后暴力A掉。

Tree

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有N个点，若VA或VB或VA+VB是质数，那么点AB的边权是min(VA,VB,|VA-VB|)，它们才可以连接。求连接所有点的边权之和，若不可连接所有的点输出-1.

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<algorithm>
#include<string.h>
using namespace std;
int t,n;
int a[605];
int prime[1000005],p[605];
struct node
{
	int u,v,w;
}e[180005];
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int find(int x)
{
	return p[x]==x?x:find(p[x]);
}
int read()
{
	int x=0;
	char ch=getchar();
	while(ch<'0' ||ch>'9')
		ch=getchar();
	while(ch>='0' &&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
void setprime()
{
	memset(prime,-1,sizeof(prime));
	prime[0]=prime[1]=0;
	for(int i=2;i<1000000;i++)
		if(prime[i]==-1)
			for(int temp=2*i;temp<=1000000;temp+=i)
				prime[temp]=0;
}
void kruskal(int top)
{
	int k=0,ans=0,x,y;
	for(int i=1;i<=n;i++)
		p[i]=i;
	for(int i=1;i<=top;i++)
	{
		if(k==n-1)
			break;
		x=find(e[i].u),y=find(e[i].v);
		if(x!=y)
		{
			ans+=e[i].w;
			p[x]=y;
			k++;
		}
	}
	printf("%d\n",k<n-1?-1:ans);
}
int main()
{
	t=read();
	setprime();
	while(t--)
	{
		n=read();
		int top=0;
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				if(prime[a[i]] || prime[a[j]] || prime[a[i]+a[j]])
				{
					e[++top].w=min(min(a[i],a[j]),abs(a[i]-a[j]));
					e[top].u=i;
					e[top].v=j;
				}
		sort(e+1,e+1+top,cmp);
		kruskal(top);
	}
	return 0;
}

思路

最小生成树即可AC。
保存边集的点和权值后使用kruskal算法即可。素数的判断使用了数组，数组的索引就是范围内的所有整数，若为素数值为1，否则为0.

注意事项

注意k=n-1时退出循环，输出是判断k是否等于k-1相当于连接了所有点，不满足输出-1.

Max Sum of Max-K-sub-sequence

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有一个“环状”数组，求最大长度不超过k的连续子串和的最大值，并输出起始和终止位置。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9;
int a[N],sum[N << 1];
struct node{
    int x,id;
}q[N << 1];
int n,k;
void dull()
{
    int f = 0,r = 0;
    int ans = -INF,s,e;
    for(int i = 1; i <= (n << 1); ++i)
	{
        while(f < r && q[r - 1].x < sum[i]) 
			--r;
        q[r].x = sum[i],q[r++].id = i;
		while(f < r && i - q[f].id >= k)
			++f;
        if(i >= k && q[f].x - sum[i - k] > ans)
		{
            ans = q[f].x - sum[i - k];
            s = i - k + 1;
            e = q[f].id;
        }
    }
    printf("%d %d %d\n",ans,(s > n ? s - n : s),(e > n ? e - n : e));
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        sum[0] = 0,sum[n + 1] = 0;
        for(int i = 1; i <= n; ++i){
            scanf("%d",&a[i]);
            sum[i] = sum[i-1] + a[i];
        }
        for(int i = n + 1; i <= (n << 1); ++i) sum[i] = sum[i-1] + a[i - n];
        dull();
    }
    return 0;
}

思路

单调队列即可AC。
代码中为了解决环状问题数组扩充了两倍，但其实只需扩充k-1位即可。
求出前缀和数组sum后进行单调队列最关键的四部操作:（顺序可交换）（因为求最大值所以要保证队列递减）
1.队头出队：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，
直到队尾的元素大于v,这个时候我们才将v插入到队尾。
2.队尾出队：由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已
经不在窗里面了。所以当index[队首元素]<i-k+1时，将队首元素删除。
3.记录头/尾的位置
4.保存max：单调队列至i的时候，此时单调队列记录的是i-k+1到i中的sum的最大值，那么[i-k+1,i]这一段的最大sum值其实是q[f]-sum[i-k],其中q[f]是单调队列的队列首
元素，也就是最大值。然后用ans记录比较最大值即可。

注意事项

理解单调队列的出队是解题的关键。
附上单调队列的最简单应用：一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>  
#include<queue>   
using namespace std;   
struct Node  
{  
    int val;  
    int index;  
};  
void GetMax(int *numSequence,int len, int *result,int k)  
{  
    Node *que = new Node[len];  
    int head = 0;  
    int end = 0;  
    for(int i=0;i<len;i++)  
    {  
        Node tmp;  
        tmp.val = numSequence[i];  
        tmp.index = i;  
        while(end!=0 && que[end].val<=numSequence[i])  
            --end;  
        ++end;  
        que[end] = tmp;  
        while(end!=0 && que[head].index<i-k+1)  
            ++head;  
        result[i] = que[head].val;  
    }     
}  
int main()  
{  
    int len, k;  
    cin>>len>>k;  
    int *numSequence = new int[len];  
    int *maxResult = new int[len];  
    for(int i=0;i<len;i++)  
        cin>>numSequence[i];  
    GetMax(numSequence,len,maxResult,k);  
    for(int i=k-1;i<len;i++)  
        cout<<i<<": "<<maxResult[i]<<endl;  
    return 0;  
}

Candy Sharing Game

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

N个人围成一圈手拿偶数个糖果，每次下达指令后所有人把自己一半的糖果给自己右边的人，若自己手上的糖果为奇数则+1，求最后下达多少次指令后所有人的糖果数才相等，
并输出糖果数。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
using namespace std;
int f(int a[],int n)
{
	for(int i=0;i<n-1;i++)
		if(a[i]!=a[i+1])
			return 1;
	return 0;
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		int a[500],flag=0;
		for(int i=0;i<n;i++)
			cin>>a[i];
		while(f(a,n))
		{
			flag++;
			int temp=a[n-1]/2;
			for(int i=n-1;i>0;i--)
			{
				a[i]=a[i]/2+a[i-1]/2;
				if(a[i]&1)
					a[i]++;
			}
			a[0]=a[0]/2+temp;
			if(a[0]&1)
				a[0]++;
		}
		cout<<flag<<" "<<a[0]<<endl;
	}
	return 0;
}

思路

模拟题。
每个人在给出一半后才可以接受别人的糖果。for循环遍历后考虑头尾成环的特殊情况即可。

注意事项

环状拉成数组。

Tr A

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
    int m[11][11];
}Matrix;
Matrix init, unit;  //初始化输入矩阵，单位矩阵如果用递归写Pow函数可以不用单位矩阵
int n, K;
void Init( )  //初始化
{
    scanf( "%d%d", &n, &K );
    for( int i=0; i<n; ++ i )
        for( int j=0; j<n; ++ j )
        {
            scanf( "%d", &init.m[i][j] );
            unit.m[i][j]=( i == j );
        }
}
Matrix Mul( Matrix a, Matrix b )  //矩阵乘法
{
    Matrix c;
    for( int i=0; i<n; ++ i )
        for( int j=0; j<n; ++ j )
        {
            c.m[i][j]=0;  //特别注意
            for( int k=0; k<n; ++ k )
                c.m[i][j] += a.m[i][k]*b.m[k][j];
            c.m[i][j] %= 9973;
        } 
    return c;
}
Matrix Pow( Matrix a, Matrix b, int k )
{
    while( k>1 )
    {
        if( k&1 )  // k为奇数时
        {
            k --;
            b=Mul( a, b );
        }
        else   // k为偶数
        {
            k >>= 1;
            a=Mul( a, a );
        }
    }
    a=Mul( a, b );
    return a;
}
int main( )
{
    int T;
    scanf( "%d", &T );
    while( T -- )
    {
        Matrix x;
        Init( );
        x=Pow( init, unit, K );
        int sum=0, i=0;
        n--;
        while( n >= 0 )
        {
            sum += x.m[n][n];
            sum%=9973;
            n --;    
        }
        printf( "%d\n", sum%9973 );
    }
}

思路

由于矩阵乘法具有结合律，因此A^4 = A A A A = (AA) (AA) = A^2 A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) A^(n/2)；当n为奇数时，
A^n = A^(n/2) A^(n/2) A （其中n/2取整）。这就告诉我们，计算A^n也可以使用二分快速求幂的方法。例如，为了算出A^25的值，我们只需要递归地计算出A^12、
A^6、A^3的值即可。
递归实现POW函数

1
2
3
4
5
6
7
8
9
10
11
Matrix POW( Matrix t,int k )
{
       if( k == 1 )
           return t;
       Matrix t1 = POW( t, k/2 );
       t1 = t1*t1;
       if( k & 1 )
           return t1 * t;
       else
           return t1;
}

递归的容易理解，但时间花费较多。所以很少用

注意事项

了解矩阵乘法的基本规则。

以下给出矩阵运算的模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct Matrix
{
    int matrix[15][15];
};
int n;     //维度,即矩阵A的行列数
int MOD=9973;//好多问题要求给出取余之后的数字
Matrix E;
void initE()    //初始化单位阵
{
    for(int i=0;i<15;i++)
        E.matrix[i][i]=1;
}
Matrix operator*(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            c.matrix[i][j] = 0;
            for (k=0;k<n;k++)
                    c.matrix[i][j]+=(a.matrix[i][k]*b.matrix[k][j]);
            c.matrix[i][j]%=MOD;
        }
    }
    return c;
}
Matrix operator+(Matrix a,Matrix b)
{
    Matrix c;
    int i,j;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
            c.matrix[i][j] = a.matrix[i][j]+b.matrix[i][j];
        c.matrix[i][j]%=9973;
    }
    return c;
}
Matrix operator^(Matrix a,int x) 
{ 
     Matrix p = E,q = a; 
     while (x>=1) 
     { 
         if(x%2==1) 
             p = p*q; 
         x/=2; 
         q = q*q; 
     } 
     return p; 
}

本文标题:11-06 热身赛

文章作者:Hippopmonkey

发布时间:2016-11-09, 11:02:29

最后更新:2016-11-12, 16:47:57

原始链接:http://xuboming8.github.io/2016/11/09/11-06-热身赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 周赛（四）
    1. 1.1. A/B
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
      3. 1.1.3. 注意事项
    2. 1.2. Tree
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. Max Sum of Max-K-sub-sequence
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. Candy Sharing Game
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
      4. 1.4.4. 注意事项
    5. 1.5. Tr A
      1. 1.5.1. 参考AC代码
      2. 1.5.2. 思路
      3. 1.5.3. 注意事项
|