Fork me on GitHub

暑假训练六总结

发表于 | 分类于 | 热度 ℃  |  
字数统计 1,323 字 | 阅读时长 6 分钟

昨天也是够丢脸的，才做出来一道题还是看了别人的代码之后才反应过来。这两天XZP也一直在反省，不过人家的水平可比我高多了，张口闭口就是一堆我没听说过的东西，看来我还得多多修行。

先说一下昨天坑爹的那题。

原题链接: EOJ 3333

请你找出一个尽可能大又不大于 k 的数 x，使得这 n 个数以及 x 共 n+1 个数的最大公因数大于 1，找不到输出0。

输入为： n k

​ n个数

Examples

Input

1
2
3 5
2 6 4

Output

1
4

Input

1
2
1 5
7

Output

1
0

代码如下：

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
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int n,k;
    cin>>n>>k;
    int mymax;
    cin>>mymax;
    for(int i=1; i<n; ++i)
    {
        int temp;
        scanf("%d",&temp);
        mymax=gcd(mymax,temp);
    }
    if(mymax==1||k==1)
    {
        cout<<0<<endl;
    }
    else
    {
        set<int> v;
        v.insert(mymax);
        for(int i=2; i*i<=mymax; ++i)
        {
            if(mymax%i==0)
            {
                v.insert(i);
                mymax=mymax/i;
                --i;
            }
        }
        int MAX=0;
        for(auto each:v)
        {
            int temp=k/each*each;
            if(temp>MAX)
            {
                MAX=temp;
            }
        }
        cout<<MAX<<endl;
    }
    return 0;
}

其实思路都是对的，但有点细节没处理好，所以一直超时。

i*i<=mymax 找素因数到根号就行了。此外，这道题还得把自己放进去。

int temp=k/each*each;这里巧妙地利用了整除，比你从小到大一个个找快多了。

原题链接：EOJ3327

Input

给n个线段，m个区间，求每个区间覆盖的线段树之和。（这里的覆盖是指只要有接触就行）

Examples

Input

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

Output

1
9

Note

第 1 个区间与第 1,2,3 条线段有交集。
第 2 个区间与第 1,2 条线段有交集。
第 3 个区间与第 3,4 条线段有交集。
第 4 个区间与第 3,4 条线段有交集。

代码如下：

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int A[N],B[N],C[N],D[N];
vector<int> vec1,vec2;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1; i<=n; i++)
    {
        cin>>A[i]>>B[i];
        vec1.push_back(A[i]);
        vec2.push_back(B[i]);
    }
    sort(vec1.begin(),vec1.end());
    sort(vec2.begin(),vec2.end());
    long long int ans = n*1ll*m;
    for(int i = 1; i<=m; i++)
    {
        cin>>C[i]>>D[i];
        ans -= (vec1.end() - upper_bound(vec1.begin(),vec1.end(),D[i])) ;
        ans -= (upper_bound(vec2.begin(),vec2.end(),C[i]-1) - vec2.begin());
    }
    cout<<ans<<endl;
}

这里用到了二分STL，所以代码很简单。此外还运用了逆向思维，long long int ans = n*1ll*m;,然后再减去不符合的数量（1.线段终点在区间起点前 2.线段起点在区间终点后）。

最后对 lower_bound 和 upper_bound做一个知识点的补充：

升序排列:

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>**= key**的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> **key**的第一个元素。

降序排列:

iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值<**= key**的第一个元素。

iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值< **key**的第一个元素。

原题链接：EOJ3332

Input

输入 T

​ n 和 mod

求n个1组成的数除以mod的余数

Examples

Input

1
2
3
4
3
3 3
4 7
5 18

Output

1
2
3
0
5   
5

代码如下：

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
#include <bits/stdc++.h>
using namespace std;
long long int power(long long int a, long long int b, long long int c)
{
    if(b==0)
        return 1;
    if(b==1)
        return a%c;
    if(b%2 == 0)
    {
        long long int temp = power(a,b/2,c);
        return (temp*temp)%c;
    }
    else
    {
        long long int temp = power(a,b/2,c);
        temp = (temp*temp)%c;
        return (temp*a)%c;
    }
}
long long int func(long long int n, long long int m)
{
    if(n< 6)
    {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(n==2)
            return 11%m;
        if(n==3)
            return 111%m;
        if(n==4)
            return 1111%m;
        if(n==5)
            return 11111%m;
    }
    if(n%2 == 0)
    {
        long long int temp = func(n/2 , m)%m;
        long long int temp1 = (power(10,n/2,m)*temp + temp)%m;
        return temp1;
    }
    else
    {
        long long int temp = func(n/2 , m)%m;
        long long int temp1 = (power(10,n/2+1,m)*temp + temp*10 + 1)%m;
        return temp1;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long int n,m;
        cin>>n>>m;
        cout<<func(n,m)<<endl;
    }
    return 0;
}

这题用到了分治的思想，还有同余性质。举个例子：1111111%999 = ((1111*1000)%999+1111%999)%999。

原题链接：EOJ3331

1到n 按顺序排好，每个数都有两次机会和左边相邻的数互换位置。问能否达到给定的目标状态，如果能，输出至少交换几次，否则输出 Too chaotic。

Examples

Input

1
2
5
2 1 5 3 4

Output

1
3

Input

1
2
5
2 5 1 3 4

Output

1
Too chaotic

代码如下：

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 <bits/stdc++.h>
using namespace std;
int a[100000];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        int bribe = 0;
        bool chaotic = false;
        for(int i = 0; i < n; i++)
        {
            if(a[i]-(i+1) > 2)
            {
                chaotic = true;
                break;
            }
            for (int j = max(0, a[i]-1-1); j < i; j++)
                if (a[j] > a[i])
                    bribe++;
        }
        if(chaotic)
            printf("Too chaotic\n");
        else
            printf("%d\n",bribe);
    }
    return 0;
}

先判断有没有某个数所在的位置向左偏离超过2的，有一个都不行。

对于任意数a[i]。 a[i]-1 是原本的下标，由于每个数最多只能向左移动两格，所以比它大的数最远只会出现在它原本的位置的左边一格(a[i]-1-1)。因此只用判断a[i]-1-1到它现在的位置这段距离里有多少数比它大，有一个就次数加一。

donate the author