第一次AK写篇题解庆祝一下~~
文章目录
A.Divisibility Problem
看代码吧
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
for(scanf("%lld",&_);_;_--){
scanf("%lld%lld",&n,&m);
if(n%m==0) printf("0\n");
else {
LL ans=(n/m+1)*m;
printf("%lld\n",abs(ans-n));
}
}
}
B. K-th Beautiful String
通过枚举第一个B的位置，可以算出排名的上限，然后从n-1开始枚举直到上限大于等于m，此时在求出第二个B的位置。
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
for(scanf("%lld",&_);_;_--){
scanf("%lld%lld",&n,&m);
int pos1,pos2;
for(int i=n-1;i>=1;i--){
LL c=1ll*(n-i-1)*(n-i)/2+n-i;
//cout<<c<<endl;
if(c>=m){
pos1=i;
c=1ll*(n-i-1)*(n-i)/2;
pos2=n-(m-c)+1;
break;
}
}
//printf("%d,%d\n",pos1,pos2);
for(int i=1;i<=n;i++){
if(i==pos1||i==pos2) printf("b");
else printf("a");
}
printf("\n");
}
}
C. Ternary XOR
贪心放，没出现1之前，两边平分，出现1之后，放小的那边
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
LL _,n,m,a[maxn],b[maxn];
char s[maxn],t[maxn];
int main(){
for(scanf("%lld",&_);_;_--){
scanf("%d",&n);
scanf("%s",s+1);
int flag=0;
for(int i=1;i<=n;i++){
if(!flag){
if(s[i]=='2') {
a[i]=1;
b[i]=1;
}
else if(s[i]=='1'){
flag=1;
a[i]=1;
b[i]=0;
}
else {
a[i]=0;b[i]=0;
}
}
else {
if(s[i]=='2'){
a[i]=0;
b[i]=2;
}
else if(s[i]=='1'){
a[i]=0;
b[i]=1;
}
else {
a[i]=b[i]=0;
}
}
}
for(int i=1;i<=n;i++) printf("%d",a[i]);printf("\n");
for(int i=1;i<=n;i++) printf("%d",b[i]);printf("\n");
}
}
D. Carousel
首先想到的是把相邻的相同类型看成一个，然后12121212这么放，最后如果发现col[n]==col[1]&&a[1]!=a[n]那就把col[n]变成3，交上去后发现wa了
仔细想想发现如果中间出现相邻的相同类型的情况，那么可以借助这个中转站，将121212变成212121，这样col[n]就不会等于col[1]了（md这个地方break写错位置wa了好多发）
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
LL _,n,k,a[maxn],col[maxn],c[maxn],d[maxn];
char s[maxn],t[maxn];
int main(){
for(scanf("%lld",&_);_;_--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
int k=0;
for(int i=1;i<=n;){
int j=i+1;
col[i]=k;
while(j<=n&&a[i]==a[j]){
col[j]=k;
j++;
}
i=j;
k^=1;
}
if(col[n]==col[1]&&a[n]!=a[1]) {
int f=0;
for(int i=2;i<=n;i++){
if(col[i]==col[i-1]){
for(int j=i;j<=n;j++){
col[j]^=1;
}
f=1;
break;
}
}
if(!f) col[n]=2;
}
k=0;
for(int i=1;i<=n;i++){
k=max(1ll*k,col[i]);
}
printf("%d\n",k+1);
for(int i=1;i<=n;i++) printf("%d ",col[i]+1);
printf("\n");
}
}
E. Tree Queries
根节点肯定是向某个叶子走，那么这个过程中，所有跟他距离<=1的点有一个性质，就是他的父亲一定在这条路上，所以我们把读入的点都变成他的父亲节点，然后按深度排序后，相邻的两个点的lca一定是深度较小的那个，否则就输出NO
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
int _,n,m,fa[maxn],dep[maxn],dp[200010][30],d[maxn],k[maxn];
VI G[maxn];
void dfs(int u,int f){
fa[u]=f;
for(int v:G[u]){
if(v==f) continue;
dfs(v,u);
}
}
void bfs(int x)
{
d[x]=1;
queue<int>q;q.push(x);
int Lgn=(int)(log(n)/log(2));
while(!q.empty()){
int f=q.front();q.pop();
int len=G[f].size();
for(int i=0;i<len;i++){
int to=G[f][i];
if(!d[to]){
q.push(to);
d[to]=d[f]+1;
dp[to][0]=f;
for(int i=1;i<=Lgn;i++){
dp[to][i]=dp[dp[to][i-1]][i-1];
}
}
}
}
}
int Lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
int lgn=(int)(log(n)/log(2));
for(int i=lgn;i>=0;i--){
int to=dp[x][i];
if(d[to]>=d[y]){
x=to;
}
}
if(x==y) return x;
for(int i=lgn;i>=0;i--){
int tx=dp[x][i],ty=dp[y][i];
if(tx!=ty){
x=tx;y=ty;
}
}
return dp[x][0];
}
bool cmp(int a,int b){
return d[a]<d[b];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
dfs(1,-1);
fa[1]=1;
bfs(1);
while(m--){
int s;scanf("%d",&s);
for(int i=1;i<=s;i++){
scanf("%d",&k[i]);
k[i]=fa[k[i]];
}
sort(k+1,k+1+s,cmp);
int flag=0;
for(int i=s-1;i>=1;i--){
if(Lca(k[i],k[i+1])!=k[i]) {
flag=1;break;
}
}
if(flag) printf("NO\n");
else printf("YES\n");
}
}
F. Make k Equal
贪心，最后出现次数>=k的一定是原数列中出现过的元素，那么我们可以O(n）枚举这个元素，然后考虑怎么O(1)或O(log)求出这个元素的答案。
仔细分析一下题目的移动规律发现要想使最大/小值 变成 C，那么所有大于C的数就都得变成C+1 OR C-1（这一部分可以通过后/前缀和），然后在根据需要的个数看转移几个就行了。
最后分类讨论一下是左边全部转移还是右边全部转移就ok了
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const int N = 5e3+5;
const int mod =1e8+7;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e6+6;
LL _,n,k,a[maxn],b[maxn],c[maxn],d[maxn];
char s[maxn],t[maxn];
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) c[i]=c[i-1]+a[i];
for(int i=n;i>=1;i--) d[i]=d[i+1]+a[i];
int m=unique(b+1,b+1+n)-b-1;
LL ans=inf;
for(int i=1;i<=m;i++){
int l=lower_bound(a+1,a+1+n,b[i])-a;
int r=upper_bound(a+1,a+1+n,b[i])-a-1;
int cnt=r-l+1;
cnt=k-cnt;
if(cnt<=0) {
ans=0;break;
}
else {
LL c1=(b[i]-1)*(l-1)-c[l-1];
if(l-1>=cnt){
c1+=cnt;
ans=min(ans,c1);
}
else {
c1+=(l-1);
c1=c1+d[r+1]-(b[i]+1)*(n-r);
c1=c1+(cnt-(l-1));
//cout<<i<<','<<c1<<','<<d[r+1]<<endl;
ans=min(ans,c1);
}
c1=d[r+1]-(b[i]+1)*(n-r);
if(n-r>=cnt){
c1+=cnt;
ans=min(ans,c1);
}
else {
c1+=(n-r);
c1=c1+(b[i]-1)*(l-1)-c[l-1];
c1=c1+(cnt-(n-r));
ans=min(ans,c1);
}
}
}
printf("%lld\n",ans);
}
京公网安备 11010502036488号