Codeforces Global Round 7(A - D题解)
题意:
给你一个数n,要你找一个数>0并且它的位数等于n,并且不能被它自己的数整除(比如23,不能被2,和3整除)。
思路:
一开始构造了一个2222(n-1个2)3,wa了两发(哭了)。后面想起一个定理,只有各位数之和能被3整除这个数才能被3整除,于是我们构造这样一个数233333(n-1个3)即可。因为2只能被偶数整数,排除,各位数之和永远不能被3整除,因为永远多了个2.然后提交就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 1e5 + 10;
int ans[maxn];
int main(){
int t;
ans[1] = -1;
ans[2] = 57;
ans[3] = 239;
ans[4] = 6789;
ans[5] = 22223;
while(scanf("%d",&t)!=EOF){
while(t--){
ll n;cin>>n;
if(n <= 5)cout<<ans[n]<<endl;
else{
cout<<"2";
for(int i = 1; i <= n - 1; i++)cout<<"3";
cout<<endl;
}
}
}
}
题意:
给你一个长度为n的序列,给出b[],要你求a[].
从题目看,我们知道a推b,现在给你b要你推a,也就是一个逆过程。
a推b要一个x[],xi = max(0,x1,x2,…x(i-1)).并且x1 = 0.xi的取值生动的讲就是a数组前i-1个数的最大值,我们只需要维护这个最大值即可。
并且有a[1] = b[1] (因为x1 = 0),也就是说最大值的初始化是a[1],又知道bi = ai - xi 移项ai = bi + xi。
所有一个for维护最大值就行。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
ll b[maxn],a[maxn];
int main(){
int n;cin>>n;
for(int i = 1; i <= n; i++)cin>>b[i];
a[1] = b[1];
ll M = a[1];
for(int i = 2; i <= n; i++){
a[i] = b[i] + M;
if(a[i] > M)M = a[i];
}
for(int i = 1; i <= n; i++){
cout<<a[i]<<" ";
}
cout<<endl;
}
题意:
给你n个数,要你从[1,n]中分成k个区间,把分出来的每个区间的最大值加起来即可,并且还要求这样满足这个最大值的区间有多少种分法。
思路:
因为可以[i,i]本身做一个区间,所有使得分出的区间最大值就是,前k大值之和,这样的区间有多少个?拿一个样例[2,1,3],最大值的2 + 3,区间怎么分?{[1,1],[2,3]},{[1,2],[3,3]}。可以这样理解,2,3中间夹了一个数,这个数对于2而言,我可以不取,也可以取一个,取完对于3而言就唯一确定了。那么取得个数就是两两最大值时间间隔了多少数,然后分部乘法原理乘起来即可。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 2e5 + 10;
const int mod = 998244353;
ll p[maxn],a[maxn];
bool cmp(ll a,ll b){
return a > b;
}
int main(){
int n,k;cin>>n>>k;
set<ll>st;
for(int i = 1; i <= n; i++)cin>>p[i],a[i] = p[i];
sort(p + 1,p + 1 + n,cmp);
long long ans = 0;
for(int i = 1 ; i <= k; i++)ans = ans + p[i],st.insert(p[i]);
ll cnt = 1;
int x1 = 0,x2 = 0;
bool flag = true;
for(int i = 1; i <= n; i++){
if(st.find(a[i])!=st.end()){
if(flag == true){
flag = false;
x1 = i;
}else{
x2 = i;
cnt = cnt * ((x2 - x1 - 1) + 1 )%mod;
x1 = x2;
}
}
}
cout<<ans<<" "<<cnt%mod<<endl;
}
菜鸡场上只写了三题,第四题场后大佬教的。
题意:
给你一个字符串要你找到一个最长的回文串,并且满足回文串是由这个串的前后缀组成。
思路:
最长回文很容易想到马拉车,不过还要满足这个串是由前后缀组成,所有我们可以先预处理一下相同的前后缀,然后把相同的部分去掉,剩下的字符串跑一遍马拉车找到最长回文串并且这个回文串在前缀或者后缀的边缘即可。
总结:思路也不是很难,开始前后缀没看懂。。。细节也需要好好处理一下。。。memset超时了改for才过(小声bb)
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char t[maxn * 2],s[maxn * 2];
int p[maxn * 2];
int len2;
void init(int l,int r){
s[0] = '@';
s[1] = '#';
int k = 2;
for(int i = l;i <= r; i++){
s[k++] = t[i];
s[k++] = '#';
}
len2 = k;
s[len2]=0;
}
int mancher(){
int id=0,mx=0;
p[0]=0;
int M = 0;
int ip = 0;
for(int i = 1; i < len2; i++){
if(mx>i){
p[i]=min(mx-i,p[2*id-i]);
}else{
p[i]=1;
}
while(s[i+p[i]] == s[i-p[i]])p[i]++;
if(i+p[i]>mx){
mx=i+p[i];id=i;
if(p[i] > M && (p[i] == i || i + p[i] == len2)){
M = p[i];ip = i;
}
}
}
return ip;
}
//abcdfdcecba
int main(){
int T;scanf("%d",&T);
while(T--){
getchar();scanf("%s",t+1);
int len1=strlen(t+1);
int l = 1 ,r = len1;
while(t[l] == t[r] && l <= r){
l++;r--;
}
if(l > r){
printf("%s\n",t+1);continue;
}
init(l,r);
int id = mancher();
for(int i = 1; i < l ; i ++)printf("%c",t[i]);
if(id >= (len2/2)){
for(int i = id - p[id] + 1; i <= len2 ; i++)
if(s[i] >= 'a' && s[i] <= 'z')printf("%c",s[i]);
}else{
for(int i = 1 ; i <= id + p[id] - 1; i++)
if(s[i] >= 'a' && s[i] <= 'z')printf("%c",s[i]);
}
for(int j = r + 1; j <= len1; j++)printf("%c",t[j]);
printf("\n");
for(int i = 0 ; i <= len2; i ++)p[i] = 0;
}
}
上一篇: 队列
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Global Round 9-C. Element Extermination
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Codeforces Global Round 9(A~D题解)
-
Codeforces A. Sign Flipping (思维 / 构造) (Global Round 9)
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
【Codeforces Global Round 7】A. Bad Ugly Numbers 题解
-
Codeforces Global Round 7 A. Bad Ugly Numbers
-
Codeforces Global Round 1 A. Parity