2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）

上一场CF打到心态爆炸，这几天也没啥想干的

A Math Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

You are given a positive integer n, please count how many positive integers k satisfy

Input

There are no more than 50 test cases.

Each case only contains a positivse integer n in a line.

Output

For each test case, output an integer indicates the number of positive integers k satisfy

Sample Input

1 4

Sample Output

1 2

第一题就是直接枚举啊，肯定很快就到上限了，测一下最大的最好了

是输出15，我还傻傻输出错了，本来只考虑了位数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=437893890380859375;
int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        if(n>=N)
            printf("15
");
        else
        {
            for(int k=1; k<16; k++)
            {
                ll s=1;
                for(int i=0; i<k; i++)
                    s*=k;
                if(s>n)
                {
                    printf("%d
",k-1);
                    break;
                }
            }
        }
    }
    return 0;
}

Covering

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Bob's school has a big playground, boys and girls always play games here after school.

To protect boys and girls from getting hurt when playing happily on the playground, rich boy Bob decided to cover the playground using his carpets.

Meanwhile, Bob is a mean boy, so he acquired that his carpets can not overlap one cell twice or more.

He has infinite carpets with sizes of

Input

There are no more than 5000 test cases.

Each test case only contains one positive integer n in a line.

Output

For each test cases, output the answer mod 1000000007 in a line.

Sample Input

1 2

Sample Output

1 5

经典骨牌覆盖，可以找到递推式

1 5 11 36 95 281 2245 6336 18061 51205 145601
a[n]=a[n-1]+5*a[n-2]+a[n-3]-a[n-4];

#include <stdio.h>
#include <string.h>
const int MD=1e9+7;
typedef long long LL;
struct matrix
{
    LL mat[5][5];
};
matrix matmul(matrix a,matrix b,int n)
{
    int i,j,k;
    matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            for(k=0; k<n; k++)
            {
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MD;
            }
        }
    }
    return c;
}
matrix matpow(matrix a,LL k,int n)
{
    matrix b;
    int i;
    memset(b.mat,0,sizeof(b.mat));
    for(i=0; i<n; i++) b.mat[i][i]=1;
    while(k)
    {
        if(k&1) b=matmul(a,b,n);
        a=matmul(a,a,n);
        k>>=1;
    }
    return b;
}
int main()
{
    LL k;
    matrix a,b;
    memset(a.mat,0,sizeof(a.mat));
    memset(b.mat,0,sizeof(b.mat));
    a.mat[0][0]=1,a.mat[2][0]=1,a.mat[3][0]=1;
    b.mat[0][0]=1,b.mat[0][1]=5,b.mat[0][2]=1,b.mat[0][3]=-1;
    b.mat[1][0]=1,b.mat[2][1]=1,b.mat[3][2]=1;
    while(~scanf("%lld",&k))
    {
        printf("%lld
",(matmul(matpow(b,k,4),a,4).mat[0][0]+MD)%MD);
    }
    return 0;
}

CS Course

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Little A has come to college and majored in Computer and Science.

Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.

Here is the problem:

You are giving n non-negative integers

Input

There are no more than 15 test cases.

Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.

Output

For each query p, output three non-negative integers indicates the result of bit-operations(and, or, xor) of all non-negative integers except

Sample Input

3 3 1 1 1 1 2 3

Sample Output

1 1 0 1 1 0 1 1 0

异或最简单，再异或一次就好了

所以按位存储了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(b,0,sizeof(b));
        int Xor=0,And=0xffffffff,Or=0;
        for(int i=1; i<=n; i++)
        {
            int x;
            scanf("%d",&x);
            a[i]=x;
            And&=x;
            Or|=x;
            Xor^=x;
            for(int j=0; x; j++,x>>=1)
                b[j]+=x%2;
        }
        while(m--)
        {
            int q;
            scanf("%d",&q);
            q=a[q];
            int A=And,O=Or,X=Xor;
            X=X^q;
            for(int j=0; j<=30; j++,q>>=1)
            {
                if(b[j]==n-1&&q%2==0)A+=(1<<j);
                if(b[j]==1&&q%2)O-=(1<<j);
            }
            printf("%d %d %d
",A,O,X);
        }
    }
    return 0

Duizi and Shunzi

Nike likes playing cards and makes a problem of it.

Now give you n integers,

a_{i} (1 \leq i \leq n)

InputThe input contains several test cases.

For each test case, the first line contains one integer n( $1 \leq n \leq 10^{6}$ OutputFor each test case, output the answer in a line.
Sample Input

7
1 2 3 4 5 6 7
9
1 1 1 2 2 2 3 3 3
6
2 2 3 3 3 3 
6
1 2 3 3 4 5

Sample Output

Hint

Case 1（1，2，3）（4，5，6）

Case 2（1，2，3）（1，1）（2，2）（3，3）

Case 3（2，2）（3，3）（3，3）

Case 4（1，2，3）（3，4，5）

这个题看起来很简单，问你最多可形成多少个对子和顺子

可是有坑啊，可以按照对子打，也可以按照顺子打，我当然按照对子打了，但是按照对子打可能我的顺子就没了，所以我首先是要打足够多的牌

比如我往下贪心的时候，如果第二张恰好是对子，我贪心就亏了，但是我下一张正好三张我肯定就要了这个顺子

所以就是记录顺子和找对子了

#include <stdio.h>
#include <string.h>
const int N=1e5+5;
int a[N];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(int)*(n+5));
        for(int i=0; i<n; i++)
        {
            int x;
            scanf("%d",&x);
            a[x]++;
        }
        int ans=0;
        for(int i=1; i<n-1; i++)
        {
            ans+=a[i]/2;
            if(a[i]&1&&a[i+1]&1&&a[i+2])
            {
                ans++;
                a[i+1]--;
                a[i+2]--;
            }
        }
        ans+=a[n-1]/2+a[n]/2;
        printf("%d
",ans);
    }
    return 0;
}