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).
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
Recommend
题意：
给一个矩形区域告诉你它的长和宽。然后两个坐标系。一个为左下角为原点。右上为正方向。一个右上角为原点。右下为正方向。现在给你一个坐标(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:
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)$.
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
Recommend
题意：
给你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.
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
Recommend
题意：
给你一个长度不超过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.
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.
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
Recommend
题意：
给你一个长度不超过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))的做法常数太大了。
看到这题。喜出望外。今天是可以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;
}