首页 > 代码库 > BestCoder Round #11 (Div. 2)题解集合

BestCoder Round #11 (Div. 2)题解集合

2024-07-25 00:14:54   221人阅读

Alice and Bob

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


Problem Description
Bob and Alice got separated in the Square, they agreed that if they get separated, they‘ll meet back at the coordinate point (x, y). Unfortunately they forgot to define the origin of coordinates and the coordinate axis direction. Now, Bob in the lower left corner of the Square, Alice in the upper right corner of the the Square. Bob regards the lower left corner as the origin of coordinates, rightward for positive direction of axis X, upward for positive direction of axis Y. Alice regards the upper right corner as the origin of coordinates, leftward for positive direction of axis X, downward for positive direction of axis Y. Assuming that Square is a rectangular, length and width size is N * M. As shown in the figure:

Bob and Alice with their own definition of the coordinate system respectively, went to the coordinate point (x, y). Can they meet with each other ?
Note: Bob and Alice before reaching its destination, can not see each other because of some factors (such as buildings, time poor).
 

Input
There are multiple test cases. Please process till EOF. Each test case only contains four integers : N, M and x, y. The Square size is N * M, and meet in coordinate point (x, y). ( 0 < x < N <= 1000 , 0 < y < M <= 1000 ).
 

Output
If they can meet with each other, please output "YES". Otherwise, please output "NO".
 

Sample Input
10 10 5 5
10 10 6 6
 

Sample Output
YES
NO
 

Source
BestCoder Round #11 (Div. 2)
 

Recommend
heyang   |   We have carefully selected several similar problems for you:  5053 5052 5051 5050 5049 
 题意：
给一个矩形区域告诉你它的长和宽。然后两个坐标系。一个为左下角为原点。右上为正方向。一个右上角为原点。右下为正方向。现在给你一个坐标(x,y)问你在两种坐标系中他们是不是表示同一个点。
思路：
把不同的坐标系转换到同一坐标系就行了。我是把左上角转换到右下角的。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;

int main()
{
    int n,m,x,y;

    while(~scanf("%d%d%d%d",&n,&m,&x,&y))
    {
        if(x==n-x&&y==m-y)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Bob and math problem

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


Problem Description
Recently, Bob has been thinking about a math problem.
There are N Digits, each digit is between 0 and 9. You need to use this N Digits to constitute an Integer.
This Integer needs to satisfy the following conditions:
  • 1. must be an odd Integer.
  • 2. there is no leading zero.
  • 3. find the biggest one which is satisfied 1, 2.

Example:
There are three Digits: 0, 1, 3. It can constitute six number of Integers. Only "301", "103" is legal, while "130", "310", "013", "031" is illegal. The biggest one of odd Integer is "301".
 

Input
There are multiple test cases. Please process till EOF.
Each case starts with a line containing an integer N ( 1 <= N <= 100 ).
The second line contains N Digits which indicate the digit $a_1, a_2, a_3, \cdots, a_n. ( 0 \leq a_i \leq 9)$.
 

Output
The output of each test case of a line. If you can constitute an Integer which is satisfied above conditions, please output the biggest one. Otherwise, output "-1" instead.
 

Sample Input
3
0 1 3
3
5 4 2
3
2 4 6
 

Sample Output
301
425
-1
 

Source
BestCoder Round #11 (Div. 2)
 

Recommend
heyang   |   We have carefully selected several similar problems for you:  5053 5052 5051 5050 5049 
 
题意：
给你n个数字要你组成n位数的最大的一个奇数。不行就输出-1.
思路：
开始读错题意了。以为输出的不一定要用到所有数字。于是判完后就挂了。真搞不懂怎么过开始的数据的。。。
这题贪心构造就行了。先找一个最小的奇数来做个位如果没有的话就-1。然后把剩下的数排序。如果剩下的还有数字且最大的为0的话肯定输出-1了。不是的话就按降序输出在加上那会找的奇数就行了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int arr[150],brr[150];
int main()
{
    int n,i,p,ct;

    while(~scanf("%d",&n))
    {
        ct=0,p=-1;
        for(i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
            if(arr[i]&1)
            {
                if(p==-1||arr[i]<arr[p])
                    p=i;
            }
        }
        if(p==-1)
        {
            printf("-1\n");
            continue;
        }
        for(i=0;i<n;i++)
            if(i!=p)
                brr[ct++]=arr[i];
        sort(brr,brr+ct);
        if(ct&&brr[ct-1]==0)
        {
            printf("-1\n");
            continue;
        }
        for(i=ct-1;i>=0;i--)
            printf("%d",brr[i]);
        printf("%d\n",arr[p]);
    }
    return 0;
}

Boring count

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


Problem Description
You are given a string S consisting of lowercase letters, and your task is counting the number of substring that the number of each lowercase letter in the substring is no more than K.
 

Input
In the first line there is an integer T , indicates the number of test cases.
For each case, the first line contains a string which only consist of lowercase letters. The second line contains an integer K.

[Technical Specification]
1<=T<= 100
1 <= the length of S <= 100000
1 <= K <= 100000
 

Output
For each case, output a line contains the answer.
 

Sample Input
3
abc
1
abcabc
1
abcabc
2
 

Sample Output
6
15
21
 

Source
BestCoder Round #11 (Div. 2)
 

Recommend
heyang   |   We have carefully selected several similar problems for you:  5053 5052 5051 5050 5049 
 
题意：
给你一个长度不超过1e5由小写组成的字符串。问你它有多少个子串。满足子串的每个字符出现的次数都不超过k。
思路：
对于一个满足条件的左端点le。把右端点ri的字符一个一个的加进去。如果还是满足条件。这个新加进的字符将会贡献ri-le+1个以该子符为右端点的子串。如果不满足条件了就左移le指针知道满足条件即可。比赛时早就想到思路了。可各种逻辑错误1小时+才1A。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100002;
typedef long long ll;
char txt[maxn];
int vis[27];
ll ans=0;
int main()
{
    int t,n,k,le,ri,p;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%d",txt,&k);
        n=strlen(txt);
        ans=le=ri=0;
        memset(vis,0,sizeof vis);
        p=-1;
        while(ri<=n)
        {
            if(p==-1)
            {
                vis[txt[ri]-'a']++;
                if(vis[txt[ri]-'a']>k)
                    p=ri;
                else if(ri<n)
                    ans+=ri-le+1;
                ri++;
            }
            else
            {
                vis[txt[le]-'a']--;
                if(txt[le]==txt[p])
                    p=-1,ans+=ri-le-1;
                le++;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

Argestes and Sequence

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


Problem Description
Argestes has a lot of hobbies and likes solving query problems especially. One day Argestes came up with such a problem. You are given a sequence a consisting of N nonnegative integers, a[1],a[2],...,a[n].Then there are M operation on the sequence.An operation can be one of the following:
S X Y: you should set the value of a[x] to y(in other words perform an assignment a[x]=y).
Q L R D P: among [L, R], L and R are the index of the sequence, how many numbers that the Dth digit of the numbers is P.
Note: The 1st digit of a number is the least significant digit.
 

Input
In the first line there is an integer T , indicates the number of test cases.
For each case, the first line contains two numbers N and M.The second line contains N integers, separated by space: a[1],a[2],...,a[n]—initial value of array elements.
Each of the next M lines begins with a character type.
If type==S,there will be two integers more in the line: X,Y.
If type==Q,there will be four integers more in the line: L R D P.

[Technical Specification]
1<=T<= 50
1<=N, M<=100000
0<=a[i]<=$2^{31}$ - 1
1<=X<=N
0<=Y<=$2^{31}$ - 1
1<=L<=R<=N
1<=D<=10
0<=P<=9
 

Output
For each operation Q, output a line contains the answer.
 

Sample Input
1
5 7
10 11 12 13 14
Q 1 5 2 1
Q 1 5 1 0
Q 1 5 1 1
Q 1 5 3 0
Q 1 5 3 1
S 1 100
Q 1 5 3 1
 

Sample Output
5
1
1
5
0
1
 

Source
BestCoder Round #11 (Div. 2)
 

Recommend
heyang   |   We have carefully selected several similar problems for you:  5053 5052 5051 5050 5049 
 
题意：
给你一个长度不超过1e5的数列。你可以进行两种操作。
1.S x y。把第x个数变成y。
2.Q l r d p 。询问[l,r]中数的第d个数字是p的有多少个。
思路：
看到这题。喜出望外。今天是可以ak的节奏啊。(不知道1002会挂。。--||)。感觉典型线段树的应用。每个节点一个数组val[rt][i][j]。表示节点代表的区间里第i个数字为j的有多少个。然后欢快的写完了。写完编译运行一次通过。无任何错误和警告测样例完全正确！然后愉快的交了。然后就mle了。。。当时就傻了。一看题目内存限制。晕。居然有数据结构题目卡内存的。然后想了下树状数组开1e7空间就算是short也超了，但是想到了离线处理每一位的修改和询问。但这时已经20:20。依稀的记得20:30就要开hack了。就放弃了挣扎了。后来醒悟后还是没时间改了。虽然正解有我说的离线处理。但是总觉得还是蛮麻烦的就用分块写了。就是分成sqrt(n)块。块内直接暴力。块间利用整块信息维护快速算出答案。时间复杂度O(n*sqrt(n))。写完一交居然rank1.估计O(10*n*log(n))的做法常数太大了。
详细见代码:
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100003;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
int val[maxn][11],da[400][11][10],x;
int main()
{
    int t,n,m,i,j,le,ri,d,p,x,y,bk,ans,st,ed,lim;
    char cmd[10];

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        bk=ceil(sqrt(1.0*n));
        memset(da,0,sizeof da);
        memset(val,0,sizeof val);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            for(j=1;j<=10;j++)
            {
                val[i][j]=x%10;
                x/=10;
            }
            p=(i-1)/bk;
            for(j=1;j<=10;j++)
                da[p][j][val[i][j]]++;
        }
        for(i=0;i<m;i++)
        {
            scanf("%s",cmd);
            if(cmd[0]=='Q')
            {
                scanf("%d%d%d%d",&le,&ri,&d,&p);
                ans=0;
                st=(le-1)/bk;
                ed=(ri-1)/bk;
                if(ed-st<=1)
                {
                    for(j=le;j<=ri;j++)
                        if(val[j][d]==p)
                            ans++;
                }
                else
                {
                    lim=(st+1)*bk;
                    for(j=le;j<=lim;j++)
                        if(val[j][d]==p)
                            ans++;
                    lim=ed*bk+1;
                    for(j=lim;j<=ri;j++)
                        if(val[j][d]==p)
                            ans++;
                    for(j=st+1;j<ed;j++)
                        ans+=da[j][d][p];
                }
                printf("%d\n",ans);
            }
            else
            {
                scanf("%d%d",&x,&y);
                p=(x-1)/bk;
                for(j=1;j<=10;j++)
                {
                    if(y%10!=val[x][j])
                    {
                        da[p][j][val[x][j]]--;
                        val[x][j]=y%10;
                        da[p][j][val[x][j]]++;
                    }
                    y/=10;
                }
            }
        }
    }
    return 0;
}


BestCoder Round #11 (Div. 2)题解集合


联系
我们