BestCoder Round #11 (Div. 2)問題解決集_html/css_WEB-ITnose

アリスとボブ 制限時間: 2000/1000 MS (Java/その他) メモリ制限: 32768/32768 K (Java/その他)
総提出数: 155 承認された提出数: 110

問題説明

ボブとアリスは広場で離ればなれになってしまいました。もし離ればなれになったら座標点 (x, y) で会おうと約束しました。残念ながら、座標の原点と座標軸の方向を定義するのを忘れていました。さて、ボブは広場の左下隅におり、アリスは広場の右上隅にいます。ボブは、左下隅を座標の原点とみなし、X 軸の正の方向は右方向、Y 軸の正の方向は上方向とします。アリスは、右上隅を座標の原点、X 軸の正の方向は左方向、下方向とみなします。 Y 軸の正の方向。正方形が長方形であると仮定すると、長さと幅のサイズは N * M です。図に示すように:

ボブとアリスはそれぞれ独自の座標系の定義を持ち、座標点 (x 、y）。彼らは会うことができますか？
注: ボブとアリスは、目的地に到着する前に、いくつかの要因 (建物、時間不足など) によりお互いを見ることができません。

入力

テストケースは複数あります。 EOFまで処理してください。各テスト ケースには、N、M、x、y の 4 つの整数のみが含まれます。正方形のサイズは N * M で、座標点 (x, y) で交わります。 (0

出力

会えたら「YES」を出力してください。それ以外の場合は「NO」を出力してください。

サンプル入力

              <p class="sycode">                  10 10 5 510 10 6 6              </p>

サンプル出力

              <p class="sycode">                  YESNO              </p>

ソース

BestCoder ラウンド #11 (ディビジョン 2)

おすすめ

heyang |   私たちはあなたのためにいくつかの同様の問題を慎重に選択しました: 5053 5052 5051 5050 5049

留意点:

一つの四角形領域の報告。原点。右上が正です方向。右上の角が原点です。右下が正の方向です。 1 つの座標(x,y) において、2 つの座標系において他は同じ点を表すわけではありません。

#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;}

ボブと数学の問題

制限時間: 2000/1000 MS (Java/その他) メモリ Liミット: 32768/32768 K (Java/その他)

総提出数: 456 承認された提出数: 169

問題の説明

最近、ボブは数学の問題について考えています。 N 桁があり、各桁は 0 から 9 までです。整数を構成するには、この N 桁を使用する必要があります。
この整数は次の条件を満たす必要があります:

1.奇数の整数でなければなりません。

2.先頭にゼロはありません。

3. 1、2 を満たす最大のものを見つけます。

例:

3 つの数字があります: 0、1、3。それは 6 つの整数を構成できます。 「301」「103」のみが合法で、「130」「310」「013」「031」は違法です。奇数整数の最大のものは「301」です。

入力
テストケースは複数あります。 EOFまで処理してください。

各ケースは、整数 N ( 1 2 行目には、$a_1、a_2、a_3、cdots、a_n の数字を示す N 桁が含まれています。 ( 0 leq a_i leq 9)$。

出力

行の各テスト ケースの出力。上記の条件を満たす整数を構成できる場合は、最大のものを出力してください。それ以外の場合は、代わりに「-1」を出力します。

 

Sample Input

                      <p class="sycode">                          30 1 335 4 232 4 6                      </p>

 

Sample Output

                      <p class="sycode">                          301425-1                      </p>

 

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

                      <p class="sycode">                          3abc1abcabc1abcabc2                      </p>

 

Sample Output

                      <p class="sycode">                          61521                      </p>

 

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

                      <p class="sycode">                          15 710 11 12 13 14Q 1 5 2 1Q 1 5 1 0Q 1 5 1 1Q 1 5 3 0Q 1 5 3 1S 1 100Q 1 5 3 1                      </p>

 

Sample Output

                      <p class="sycode">                          511501                      </p>

 

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,rsint 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;}