概述
目录
A. Everyone Loves to Sleep
B - Remove Prefix
C. Minimum Varied Number
D. Color with Occurrences
E. Add Modulo 10
A. Everyone Loves to Sleep
Vlad, like everyone else, loves to sleep very much.
Every day Vlad has to do nn things, each at a certain time. For each of these things, he has an alarm clock set, the ii-th of them is triggered on hihi hours mimi minutes every day (0≤hi<24,0≤mi<600≤hi<24,0≤mi<60). Vlad uses the 2424-hour time format, so after h=12,m=59h=12,m=59 comes h=13,m=0h=13,m=0 and after h=23,m=59h=23,m=59 comes h=0,m=0h=0,m=0.
This time Vlad went to bed at HH hours MM minutes (0≤H<24,0≤M<600≤H<24,0≤M<60) and asks you to answer: how much he will be able to sleep until the next alarm clock.
If any alarm clock rings at the time when he went to bed, then he will sleep for a period of time of length 00.
Input
The first line of input data contains an integer tt (1≤t≤1001≤t≤100) — the number of test cases in the test.
The first line of the case contains three integers nn, HH and MM (1≤n≤10,0≤H<24,0≤M<601≤n≤10,0≤H<24,0≤M<60) — the number of alarms and the time Vlad went to bed.
The following nn lines contain two numbers each hihi and mimi (0≤hi<24,0≤mi<600≤hi<24,0≤mi<60) — the time of the ii alarm. It is acceptable that two or more alarms will trigger at the same time.
Numbers describing time do not contain leading zeros.
Output
Output tt lines, each containing the answer to the corresponding test case. As an answer, output two numbers — the number of hours and minutes that Vlad will sleep, respectively. If any alarm clock rings at the time when he went to bed, the answer will be 0 0.
题意： 给你一个人的睡觉时间，然后给你n个闹钟的响铃时间，问你这个人能睡几个小时几分钟。
思路：简单的模拟，但是注意小细节，为了按照时间排序方便，我们直接用一个结构体分别把小时和分钟数存起来，然后按照时间排序，然后分情况讨论，如果睡觉的时间比所有闹钟的时间要晚，那就输出第二天最早的闹钟时间与睡觉时间的差值。
如果存在闹钟时间比睡觉时间晚，那就输出睡觉时间之后最近的闹钟时间。
我的代码写的是用小时和分钟数算的，比较麻烦，这里推荐直接转化成分钟数算起来更方便，比如两点三十直接算成当天的第150分钟。
#include <bits/stdc++.h>
using namespace std;
struct node
{
int hh,mm;
}a[20];
bool cmp(struct node x,struct node y)
{
if(x.hh==y.hh)
return x.mm<y.mm;
return x.hh<y.hh;
}
int main()
{
int t,n,h,m,i;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&h,&m);
for(i=1;i<=n;i++)
{
scanf("%d %d",&a[i].hh,&a[i].mm);
}
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
if(a[i].hh>h||a[i].hh==h&&a[i].mm>=m)
break;
}
if(i<=n)
{
if(a[i].mm>=m)
printf("%d %dn",a[i].hh-h,a[i].mm-m);
else
printf("%d %dn",a[i].hh-h-1,60-m+a[i].mm);
}
else
{
if(a[1].mm>=m)
printf("%d %dn",a[1].hh+24-h,a[1].mm-m);
else
printf("%d %dn",a[1].hh+24-h-1,60-m+a[1].mm);
}
}
return 0;
}B - Remove Prefix
Polycarp was presented with some sequence of integers aa of length nn (1≤ai≤n1≤ai≤n). A sequence can make Polycarp happy only if it consists of different numbers (i.e. distinct numbers).
In order to make his sequence like this, Polycarp is going to make some (possibly zero) number of moves.
In one move, he can:
- remove the first (leftmost) element of the sequence.
For example, in one move, the sequence [3,1,4,3][3,1,4,3] will produce the sequence [1,4,3][1,4,3], which consists of different numbers.
Determine the minimum number of moves he needs to make so that in the remaining sequence all elements are different. In other words, find the length of the smallest prefix of the given sequence aa, after removing which all values in the sequence will be unique.
Input
The first line of the input contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
Each test case consists of two lines.
The first line contains an integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of the given sequence aa.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n) — elements of the given sequence aa.
It is guaranteed that the sum of nn values over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case print your answer on a separate line — the minimum number of elements that must be removed from the beginning of the sequence so that all remaining elements are different.
题意：给你一串序列，每次操作会删除最左边的元素，问你操作几次会让剩下的所有元素都各不相同。
思路：从后往前遍历，如果遇到的元素是第一次出现，就continue，如果是第二次出现，就break， 然后这个元素之前的（包括这个元素）所有数就都是我们要删除的。
（我写的代码有点麻烦了，纯纯脱裤子放屁）
#include <bits/stdc++.h>
using namespace std;
int a[200010],b[200010],st[200010];
int main()
{
int t,n,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(b,0,sizeof(b));
memset(st,0,sizeof(st));
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for(i=n;i>=1;i--)
{
if(b[a[i]]>1&&st[a[i]]==0)
st[a[i]]=1;
else if(st[a[i]]==1)
break;
}
if(i>=1)
printf("%dn",i);
else
printf("0n");
}
return 0;
}C. Minimum Varied Number
Find the minimum number with the given sum of digits ss such that all digits in it are distinct (i.e. all digits are unique).
For example, if s=20s=20, then the answer is 389389. This is the minimum number in which all digits are different and the sum of the digits is 2020 (3+8+9=203+8+9=20).
For the given ss print the required number.
Input
The first line contains an integer tt (1≤t≤451≤t≤45) — the number of test cases.
Each test case is specified by a line that contains the only integer ss (1≤s≤451≤s≤45).
Output
Print tt integers — the answers to the given test cases.
题意：给你一个n，让你求一个数s，要求s的每一位数字加起来等于n，s的各位数不能有重复的，并且s是所有满足条件的数字里最小的。
思路：直接枚举，想让s最小，同时各位数字加起来等于n，那么最好的情况就是最高位小，最低位大，而且位数少，比方说若n=20，那么，389，938，1289，44444这三种情况的各位数字加起来都是等于20的，那我们就会发现389是最小的，没有重复的，所以我们可以直接枚举所有情况。
#include <bits/stdc++.h>
using namespace std;
int a[200010],b[200010],st[200010];
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n>=1&&n<=9)
printf("%dn",n);
else if(n>=10&&n<=17)
printf("%d9n",n-9);
else if(n>=18&&n<=24)
printf("%d89n",n-17);
else if(n>=25&&n<=30)
printf("%d789n",n-24);
else if(n>=31&&n<=35)
printf("%d6789n",n-30);
else if(n>=36&&n<=39)
printf("%d56789n",n-35);
else if(n>=40&&n<=42)
printf("%d456789n",n-39);
else if(n>=43&&n<=44)
printf("%d3456789n",n-42);
else
printf("123456789n");
}
return 0;
}D. Color with Occurrences
You are given some text tt and a set of nn strings s1,s2,…,sns1,s2,…,sn.
In one step, you can choose any occurrence of any string sisi in the text tt and color the corresponding characters of the text in red. For example, if t=bababat=bababa and s1=bas1=ba, s2=abas2=aba, you can get t=bababat=bababa, t=bababat=bababa or t=bababat=bababa in one step.
You want to color all the letters of the text tt in red. When you color a letter in red again, it stays red.
In the example above, three steps are enough:
- Let's color t[2…4]=s2=abat[2…4]=s2=aba in red, we get t=bababat=bababa;
- Let's color t[1…2]=s1=bat[1…2]=s1=ba in red, we get t=bababat=bababa;
- Let's color t[4…6]=s2=abat[4…6]=s2=aba in red, we get t=bababat=bababa.
Each string sisi can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.
Determine the minimum number of steps needed to color all letters tt in red and how to do it. If it is impossible to color all letters of the text tt in red, output -1.
题意： 给你一个母串s，一堆字串ss，每次可以选择一个字串ss，把母串s里面与ss完全相同的染成红色，为你如果不能全部染成红色，就输出-1，如果可以，输出最小的操作次数k，然后接下来k行输出每次选择哪个字串，从哪个下标开始染。
思路：因为这题给的数据范围很小，所以可以直接暴力，从母串s从头到尾遍历，每次都取能染色最多的字串，然后push进队列里面。
#include <bits/stdc++.h>
#include <string>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
queue<PII> q;
int main()
{
int st[110];
int t, i, n, j,kk,kkk,kkkk;
int lenn[110];
string s, ss[110];
scanf("%d", &t);
while (t--)
{
memset(st,0,sizeof(st));
cin>>s;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
cin>>ss[i];
lenn[i] = ss[i].length();
}
int len = s.length();
int k = 0;
for (j = 1; j <= n; j++)
{
if (lenn[j] > len)
continue;
string t = s.substr(0, lenn[j]);
if (t == ss[j])
{
if (lenn[j] > k)
{
k = lenn[j];
kkkk=j;
}
}
}
if (k == 0)
{
printf("-1n");
continue;
}
else
{
for (i = 0; i < k; i++)
{
st[i] = 1;
}
q.push({kkkk, 1});
}
int r=k-1;
for (i = 1; i < len; i++)
{k = 0;
while (st[i - 1] == 1)
{
for (j = 1; j <= n; j++)
{
if (i + lenn[j] > len)
continue;
string t = s.substr(i, lenn[j]);
//cout<<t<<endl;
if (t == ss[j]&&i+lenn[j]-r-1>k)
{
k=i+lenn[j]-r-1;
kk=i;
kkk=lenn[j];
kkkk=j;
}
}
i++;
}
i--;
if(k==0)
break;
q.push({kkkk,kk+1});
for(j=kk;j<=kk+kkk-1;j++)
st[j]=1;
r=kk+kkk-1;
if(r==len-1)
break;
i=kk;
}
if(i<len&&r!=len-1)
{
while(!q.empty())
q.pop();
printf("-1n");
continue;
}
printf("%dn",q.size());
while(!q.empty())
{
printf("%d %dn",q.front().first,q.front().second);
q.pop();
}
}
return 0;
}
E. Add Modulo 10
You are given an array of nn integers a1,a2,…,ana1,a2,…,an
You can apply the following operation an arbitrary number of times:
- select an index ii (1≤i≤n1≤i≤n) and replace the value of the element aiai with the value ai+(aimod10)ai+(aimod10), where aimod10aimod10 is the remainder of the integer dividing aiai by 1010.
For a single index (value ii), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of aiai is taken into account each time. For example, if ai=47ai=47 then after the first operation we get ai=47+7=54ai=47+7=54, and after the second operation we get ai=54+4=58ai=54+4=58.
Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.
For example, you have an array [6,11][6,11].
- Let's apply this operation to the first element of the array. Let's replace a1=6a1=6 with a1+(a1mod10)=6+(6mod10)=6+6=12a1+(a1mod10)=6+(6mod10)=6+6=12. We get the array [12,11][12,11].
- Then apply this operation to the second element of the array. Let's replace a2=11a2=11 with a2+(a2mod10)=11+(11mod10)=11+1=12a2+(a2mod10)=11+(11mod10)=11+1=12. We get the array [12,12][12,12].
Thus, by applying 22 operations, you can make all elements of an array equal.
Input
The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. What follows is a description of each test case.
The first line of each test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the size of the array.
The second line of each test case contains nn integers aiai (0≤ai≤1090≤ai≤109) — array elements.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case print:
- YES if it is possible to make all array elements equal;
- NO otherwise.
You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .
题意：给你一个序列，每次操作可以让一个数a[i]加上它各位上的数，问你是否最后能让所有数相同。
思路：自己在纸上演示一遍就知道了，当末尾数字是1时，会形成一个循环：1>>2>>4>>8>>6>>2>>4>>8>>......
然后我们发现当8->6的时候是需要进位，同时6->2的时候也是需要进位的，所以我们可以认为1，2，4，8是一类的，当他们之间的十位同时都是偶数，或者同时都是奇数的时候，他们必定可以变成同样的数。
有点抽象，打个比方吧，比如1，2，4，8，22是可以的，22，21，48，42也是可以的，但是21，32，34，38是不行的，因为21的十位是偶数，但是其他三个是奇数。
再想其他的情况，如果末位数字是3时，也会形成一个循环3>>6>>2>>4>>8>>6>>2>>4>>8>>......
同样的我们会发现，3和6是一类的，2，4，8是一类的。
如果末位数字是7，循环时7>>4>>8>>6>>2，7和6是一类的。7到4会进位，8到6会进位。
末位数字是9，循环是9>>8>>6>>2>>4>>8>>.....9和6一类，9到8会进位，8到6会进位。
至此我们除了5和0，会发现，其他的所有数都可归为两个大类，末尾数字是3，6，7，9的和末位数字是1，2，4，8。
然后是5，0的情况，我们发现当末位数字是0的时候，它是不可能发生变化的，当末位数字是0时，他最多只能进行一次操作，加5之后变成0也就不能再操作了。
分析结束，然后是代码实现。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll a[200010];
int main()
{
ll t,n,i;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
if(n==1)
{
scanf("%d",&a[i]);
printf("Yesn");
continue;
}
for(i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
}
if(a[1]%10==1||a[1]%10==2||a[1]%10==4||a[1]%10==8)
{
for(i=2; i<=n; i++)
{
if((a[i]%10==6||a[i]%10==3||a[i]%10==7||a[i]%10==9)&&(abs(a[i]/10-a[1]/10))%2==1)
continue;
else if((a[i]%10==2||a[i]%10==4||a[i]%10==1||a[i]%10==8)&&(abs(a[i]/10-a[1]/10))%2==0)
continue;
else
break;
}
if(i<=n)
printf("Non");
else
printf("Yesn");
}
else if(a[1]%10==3||a[1]%10==6||a[1]%10==7||a[1]%10==9)
{
for(i=2; i<=n; i++)
{
if((a[i]%10==6||a[i]%10==3||a[i]%10==7||a[i]%10==9)&&(abs(a[i]/10-a[1]/10))%2==0)
continue;
else if((a[i]%10==2||a[i]%10==4||a[i]%10==1||a[i]%10==8)&&(abs(a[i]/10-a[1]/10))%2==1)
continue;
else
break;
}
if(i<=n)
printf("Non");
else
printf("Yesn");
}
else if(a[1]%10==5)
{
for(i=2; i<=n; i++)
{
if(a[i]%10==0&&a[i]-a[1]!=5)
break;
else if(a[i]%10==5&&a[i]!=a[1])
break;
else if(a[i]%10!=0&&a[i]%10!=5)
break;
}
if(i<=n)
printf("Non");
else
printf("Yesn");
}
else if(a[1]%10==0)
{
for(i=2;i<=n;i++)
{
if(a[i]%10==5&&a[i]<a[1]&&a[1]-a[i]==5)
continue;
if(a[i]!=a[1])
break;
}
if(i<=n)
printf("Non");
else
printf("Yesn");
}
}
return 0;
}最后
以上就是炙热汉堡为你收集整理的(cf)Codeforces Round #811 (Div. 3)A--E详细题解A. Everyone Loves to Sleep B - Remove PrefixC. Minimum Varied Number D. Color with Occurrences E. Add Modulo 10的全部内容，希望文章能够帮你解决(cf)Codeforces Round #811 (Div. 3)A--E详细题解A. Everyone Loves to Sleep B - Remove PrefixC. Minimum Varied Number D. Color with Occurrences E. Add Modulo 10所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复