一个人失眠

从上一周周一学习KMP算法之后，每天晚上都失眠到1点过起夜，身体再疲倦脑子都异常清醒，要死了要死了。

kmp算法真的有毒。

这个题，我用优先队列记录最小的下标，用Map记录每个数字是第几天，然后让那个值和队列首元素比较，如果符合条件就赋相同的值，不然天数就加一。

C. Coffee Break

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Monocarp got a job. His working day lasts exactly $\mathrm{mm minutes.\; During\; work,\; Monocarp\; wants\; to\; drink\; coffee\; at\; certain\; moments:\; there\; are nn minutes a1,a2,\dots ,ana1,a2,\dots ,an,\; when\; he\; is\; able\; and\; willing\; to\; take\; a\; coffee\; break\; (for\; the\; sake\; of\; simplicity\; let\text{'}s\; consider\; that\; each\; coffee\; break\; lasts\; exactly\; one\; minute).}$

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute ${\mathrm{aiai,\; Monocarp\; must\; choose\; the\; day\; in\; which\; he\; will\; drink\; coffee\; during\; the\; said\; minute,\; so\; that\; every\; day\; at\; least dd minutes\; pass\; between\; any\; two\; coffee\; breaks.\; Monocarp\; also\; wants\; to\; take\; these nn coffee\; breaks\; in\; a\; minimum\; possible\; number\; of working days\; (he\; doesn\text{'}t\; count\; days\; when\; he\; is\; not\; at\; work,\; and\; he\; doesn\text{'}t\; take\; coffee\; breaks\; on\; such\; days).\; Take\; into\; account\; that\; more\; than dd minutes\; pass\; between\; the\; end\; of\; any\; working\; day\; and\; the\; start\; of\; the\; following\; working\; day.}}^{}$

For each of the $\mathrm{nn given\; minutes\; determine\; the\; day,\; during\; which\; Monocarp\; should\; take\; a\; coffee\; break\; in\; this\; minute.\; You\; have\; to\; minimize\; the\; number\; of\; days\; spent.}$

Input

The first line contains three integers $\mathrm{nn, mm, dd (1\le n\le 2\cdot 105,n\le m\le 109,1\le d\le m)(1\le n\le 2\cdot 105,n\le m\le 109,1\le d\le m) —\; the\; number\; of\; coffee\; breaks\; Monocarp\; wants\; to\; have,\; the\; length\; of\; each\; working\; day,\; and\; the\; minimum\; number\; of\; minutes\; between\; any\; two\; consecutive\; coffee\; breaks.}$

The second line contains $\mathrm{nn distinct\; integers a1,a2,\dots ,ana1,a2,\dots ,an (1\le ai\le m)(1\le ai\le m),\; where aiai is\; some\; minute\; when\; Monocarp\; wants\; to\; have\; a\; coffee\; break.}$

Output

In the first line, write the minimum number of days required to make a coffee break in each of the $\mathrm{nn given\; minutes.}$

In the second line, print $\mathrm{nn space\; separated\; integers.\; The ii-th\; of\; integers\; should\; be\; the\; index\; of\; the\; day\; during\; which\; Monocarp\; should\; have\; a\; coffee\; break\; at\; minute aiai.\; Days\; are\; numbered\; from 11.\; If\; there\; are\; multiple\; optimal\; solutions,\; you\; may\; print\; any\; of\; them.}$

Examples

input

Copy

4 5 3
3 5 1 2

output

Copy

3
3 1 1 2 

input

Copy

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

output

Copy

2
2 1 1 2 2 1 2 1 1 2 

Note

In the first example, Monocarp can take two coffee breaks during the first day (during minutes $\mathrm{11 and 55, 33 minutes\; will\; pass\; between\; these\; breaks).\; One\; break\; during\; the\; second\; day\; (at\; minute 22),\; and\; one\; break\; during\; the\; third\; day\; (at\; minute 33).}$

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
map<int,int>str;
priority_queue<int,vector<int>,greater <int> >que;
int a[200005],b[200005];
int main()
{
    int i,n,m,k,x;
    cin>>n>>m>>k;
    for(i=0;i<n;i++)
    {
        cin>>x;
        a[i]=x;
        b[i]=x;
    }
    que.push(0);
    sort(a,a+n);
    str[a[0]]=1;
    int cnt=1;
    for(i=1;i<n;i++)
    {
        int t=que.top();
        if(a[i]-a[t]>k)
        {
            str[a[i]]=str[a[t]];
            que.pop();
        }
        else
        {
        str[a[i]]=++cnt;
        }
        que.push(i);
    }
    cout<<cnt<<endl;
    for(i=0;i<n;i++)
    {
        if(i!=0)
            cout<<" ";
        cout<<str[b[i]];
    }
    return 0;
}

这个题就是用vector容器的使用，再通过字符串长度分类，然后取每一个的最小值分情况讨论。

B. Vitamins

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Berland shop sells $\mathrm{nn kinds\; of\; juices.\; Each\; juice\; has\; its\; price cici.\; Each\; juice\; includes\; some\; set\; of\; vitamins\; in\; it.\; There\; are\; three\; types\; of\; vitamins:\; vitamin\; "A",\; vitamin\; "B"\; and\; vitamin\; "C".\; Each\; juice\; can\; contain\; one,\; two\; or\; all\; three\; types\; of\; vitamins\; in\; it.}$

Petya knows that he needs all three types of vitamins to stay healthy. What is the minimum total price of juices that Petya has to buy to obtain all three vitamins? Petya obtains some vitamin if he buys at least one juice containing it and drinks it.

Input

The first line contains a single integer $\mathrm{nn (1\le n\le 1000)(1\le n\le 1000) —\; the\; number\; of\; juices.}$

Each of the next $\mathrm{nn lines\; contains\; an\; integer cici (1\le ci\le 100000)(1\le ci\le 100000) and\; a\; string sisi —\; the\; price\; of\; the ii-th\; juice\; and\; the\; vitamins\; it\; contains.\; String sisi contains\; from 11 to 33 characters,\; and\; the\; only\; possible\; characters\; are\; "A",\; "B"\; and\; "C".\; It\; is\; guaranteed\; that\; each\; letter\; appears\; no\; more\; than\; once\; in\; each\; string sisi.\; The\; order\; of\; letters\; in\; strings sisi is\; arbitrary.}$

Output

Print -1 if there is no way to obtain all three vitamins. Otherwise print the minimum total price of juices that Petya has to buy to obtain all three vitamins.

Examples

input

Copy

4
5 C
6 B
16 BAC
4 A

output

Copy

15

input

Copy

2
10 AB
15 BA

output

Copy

-1

input

Copy

5
10 A
9 BC
11 CA
4 A
5 B

output

Copy

13

input

Copy

6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

output

Copy

250

input

Copy

2
5 BA
11 CB

output

Copy

16

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int main()
{
    vector<int> a,b,c,ab,bc,ac,abc;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int p;
        cin>>p;

        string s;
        cin>>s;

        sort(s.begin(),s.end());

        if(s.size()==1)
        {
            if(s[0]=='A')
            {
                a.push_back(p);
            }
            else if(s[0]=='B')
            {
                b.push_back(p);
            }
            else
            {
                 c.push_back(p);
            }
        }
        else if(s.size()==2)
        {
            if(s=="AB")
            {
                ab.push_back(p);
            }
            else if(s=="BC")
            {
                bc.push_back(p);
            }
            else if(s=="AC")
            {
                 ac.push_back(p);
            }
        }
        else
        {
            abc.push_back(p);
        }
    }

    int ans = pow(10,7);


    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    sort(ab.begin(),ab.end());
    sort(ac.begin(),ac.end());
    sort(bc.begin(),bc.end());
    sort(abc.begin(),abc.end());

    if(a.size()!=0 && b.size()!=0 && c.size()!=0)
    {
        ans = min(ans,a[0]+b[0]+c[0]);
    }
     if(ab.size()!=0 && c.size()!=0)
    {
        ans = min(ans,ab[0]+c[0]);
    }
      if(bc.size()!=0 && a.size()!=0)
    {
        ans = min(ans,bc[0]+a[0]);
    }
      if(ac.size()!=0 && b.size()!=0)
    {
        ans = min(ans,ac[0]+b[0]);
    }
      if(abc.size()!=0)
    {
        ans = min(ans,abc[0]);
    }
     if(ab.size()!=0 && bc.size()!=0)
    {
        ans = min(ans,ab[0]+bc[0]);
    }
     if(ab.size()!=0 && ac.size()!=0)
    {
        ans = min(ans,ab[0]+ac[0]);
    }
     if(bc.size()!=0 && ac.size()!=0)
    {
        ans = min(ans,ac[0]+bc[0]);
    }

    if(ans==pow(10,7))
    cout<<-1<<endl;
    else
    cout<<ans<<endl;

return 0;

}

这道题要用到一定数学技巧，当m > k时输出-1（设m是较大的数），当m-n是奇数时有一步不能走对角线所以k--，当走对角线可以直接到达终点，如果是偶数，剩余的步数是奇数则有两步不能走对角线要走一个三角形，所以k - 2。

B. Diagonal Walking v.2

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mikhail walks on a Cartesian plane. He starts at the point $(0,0)(0,0),\; and\; in\; one\; move\; he\; can\; go\; to\; any\; of\; eight\; adjacent\; points.\; For\; example,\; if\; Mikhail\; is\; currently\; at\; the\; point (0,0)(0,0),\; he\; can\; go\; to\; any\; of\; the\; following\; points\; in\; one\; move:$

• $(1,0)(1,0);$
• $(1,1)(1,1);$
• $(0,1)(0,1);$
• $(-1,1)(-1,1);$
• $(-1,0)(-1,0);$
• $(-1,-1)(-1,-1);$
• $(0,-1)(0,-1);$
• $(1,-1)(1,-1).$

If Mikhail goes from the point $(x1,y1)(x1,y1) to\; the\; point (x2,y2)(x2,y2) in\; one\; move,\; and x1\ne x2x1\ne x2 and y1\ne y2y1\ne y2,\; then\; such\; a\; move\; is\; called\; a diagonal\; move.$

Mikhail has $\mathrm{qq queries.\; For\; the ii-th\; query\; Mikhail\text{'}s\; target\; is\; to\; go\; to\; the\; point (ni,mi)(ni,mi) from\; the\; point (0,0)(0,0) in exactly kiki moves.\; Among\; all\; possible\; movements\; he\; want\; to\; choose\; one\; with\; the\; maximum\; number\; of diagonal\; moves.\; Your\; task\; is\; to\; find\; the\; maximum\; number\; of diagonal\; moves or\; find\; that\; it\; is\; impossible\; to\; go\; from\; the\; point (0,0)(0,0) to\; the\; point (ni,mi)(ni,mi) in kiki moves.}$

Note that Mikhail can visit any point any number of times (even the destination point!).

Input

The first line of the input contains one integer $\mathrm{qq (1\le q\le 1041\le q\le 104)\; —\; the\; number\; of\; queries.}$

Then $\mathrm{qq lines\; follow.\; The ii-th\; of\; these qq lines\; contains\; three\; integers nini, mimi and kiki (1\le ni,mi,ki\le 10181\le ni,mi,ki\le 1018)\; — xx-coordinate\; of\; the\; destination\; point\; of\; the\; query, yy-coordinate\; of\; the\; destination\; point\; of\; the\; query\; and\; the\; number\; of\; moves\; in\; the\; query,\; correspondingly.}$

Output

Print $\mathrm{qq integers.\; The ii-th\; integer\; should\; be\; equal\; to -1 if\; Mikhail\; cannot\; go\; from\; the\; point (0,0)(0,0) to\; the\; point (ni,mi)(ni,mi) in exactly kiki moves\; described\; above.\; Otherwise\; the ii-th\; integer\; should\; be\; equal\; to\; the\; the\; maximum\; number\; of diagonal\; moves among\; all\; possible\; movements.}$

Example

input

Copy

3
2 2 3
4 3 7
10 1 9

output

Copy

1
6
-1

Note

One of the possible answers to the first test case: $(0,0)\to (1,0)\to (1,1)\to (2,2)(0,0)\to (1,0)\to (1,1)\to (2,2).$

One of the possible answers to the second test case: $(0,0)\to (0,1)\to (1,2)\to (0,3)\to (1,4)\to (2,3)\to (3,2)\to (4,3)(0,0)\to (0,1)\to (1,2)\to (0,3)\to (1,4)\to (2,3)\to (3,2)\to (4,3).$

In the third test case Mikhail cannot reach the point $(10,1)(10,1) in\; 9\; moves.$

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
int main()
{
long long t,n,m,i,k;
cin>>t;
while(t--)
{
    cin>>n>>m>>k;
    if(n>m)
        swap(n,m);
        if(m>k)
        {
            cout<<-1<<endl;
            continue;
        }
        if((m-n)%2==1)
            k-=1;
        else if((k-m)%2==1)
            k-=2;
        cout<<k<<endl;
}
return 0;
}
这道题满足左小右大原则，那么我们先从左到右遍历，设第一个数是最大值，不断更新替换，如果那个值左边比他大的数，就标记一，再设最右边是最小的数，从右往左遍历，同理。

An O(n)O(n) Partition algorithm partitions an array A around a pivot element (pivot is a member of A) into three parts: a left sub-array that contains elements that are ≤≤pivot, the pivot itself, and a right sub-array that contains elements that are >>pivot.

A Partition algorithm is an integral part of a popular sorting algorithm Quicksort. Usually, the choice of pivot is randomized so that Quicksort has an expected O(nlogn)O(nlog⁡n) running time performance.

Now the actual job in this problem is this: Starting from an array A that has nndistinct integers, we partition A using one of the member of A as pivot to produce a transformed array A’. Given this transformed array A’, your job is to count how many integers that could have been the chosen pivot.

For example, if A’ = {2,1,3,4,7,5,6,8}{2,1,3,4,7,5,6,8}, then 3 integers: {3,4,8}{3,4,8} could have been the pivot of partition, e.g. {2,1,3}{2,1,3} to the left of integer 44 are smaller than 44 and {7,5,6,8}{7,5,6,8} to the right of integer 44 are greater than 44. However, the other 5 integers cannot possibly be the pivot, e.g. integer 77 cannot possibly be the pivot as there are {5,6}{5,6} to the right of integer 77.

Input

The input consists of two lines. The first line contains integer nn (3≤n≤1000003≤n≤100000). The second line contains nn distinct 32-bit signed integers that describes the transformed array A′A′.

Output

Output the required answer as a single integer in one line.

Sample Input 1	Sample Output 1
8 2 1 3 4 7 5 6 8	3

Sample Input 2	Sample Output 2
7 1 2 3 4 5 7 6	5

#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int a[100010],vis[100010];
int main()
{
	int n,i,ans=0,j;
	cin>>n;
	for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int k=0,flag=0;
    int maxx=a[0],minn=a[n-1];
    for(i=1;i<n;i++)
    {
       if(a[i]<maxx)
        vis[i]=1;
        maxx=max(a[i],maxx);
    }
    for(i=n-2;i>=0;i--)
    {
        if(a[i]>minn)
            vis[i]=1;
        minn=min(a[i],minn);
    }
    for(i=0;i<n;i++)
    {
        if(!vis[i])
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

　　全寝室换了一朵佛系的花的头像，愿上帝保佑我，赐予我良好的睡眠。