A 小红喜欢1
小想法：5个数字，找到1即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a1,a2,a3,a4,a5;
signed main(){
//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
cin>>a1>>a2>>a3>>a4>>a5;
if(a1==1)cout<<1<<endl;
else if(a2==1)cout<<2<<endl;
else if(a3==1)cout<<3<<endl;
else if(a4==1)cout<<4<<endl;
else if(a5==1)cout<<5<<endl;
//fclose(stdin);fclose(stdout);
return 0;
}
B 小红的树切割
小想法：dfs一遍即可，当前无向边连接的两个点如果颜色相同，就切断它(ans++)，否则就不管它。
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct nod{
int u,v,next;
};
nod a[200009];
char c[200009];
int n,i,cnt,u,v,fir[100009],ans,vis[100009];
void add(int u,int v){
cnt++;
a[cnt].next=fir[u];
a[cnt].u=u;a[cnt].v=v;
fir[u]=cnt;
}
void dfs(int u){
int i;
vis[u]=1;
for(i=fir[u];i;i=a[i].next){
int v=a[i].v;
if(vis[v]==0){
if(c[u]!=c[v])ans++;
dfs(v);
}
}
}
signed main(){
//freopen("2.in","r",stdin);freopen("2.out","w",stdout);
cin>>n;getchar();
for(i=1;i<=n;i++)c[i]=getchar();
for(i=1;i<n;i++){
scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dfs(1);
cout<<ans<<endl;
//fclose(stdin);fclose(stdout);
return 0;
}
C 小红的双好数（easy）
小想法：演算发现，本题一共分为三种情况。(注意一下k1<k2)
当n==1时，k1与k2随便取都行。
当n==2时，无解。
当n>=3时，取k1=n-1，k2=n就满足题意了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k1,k2;
signed main(){
//freopen("3.in","r",stdin);freopen("3.out","w",stdout);
cin>>n;
if(n==2)cout<<"NO"<<endl;
else if(n==1){
cout<<"YES"<<endl;
k1=3;k2=4;
cout<<k1<<' '<<k2<<endl;
}
else{
cout<<"YES"<<endl;
k1=n-1;k2=n;
cout<<k1<<' '<<k2<<endl;
}
//fclose(stdin);fclose(stdout);
return 0;
}
D 小红的线段
这题我好像想得有些复杂了。。。
我的思路就是把点分为三类，在直线上方，在直线下方，位于直线上。
贪心地，先把直线上下方的点尽可能多地连接，再把位于直线上的点尽可能连接，剩下的点就是“没用的点”了，记录后输出即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct nod{
int x,y,bh;
};
nod s[2009],xia[2009],r[2009],yes[2009],no[2009];
int n,k,b,i,x,y,C,j,cnt,nocnt;
int scnt,xcnt,rcnt;
signed main(){
//freopen("4.in","r",stdin);freopen("4.out","w",stdout);
cin>>n>>k>>b;
for(i=1;i<=2*n;i++){
scanf("%lld%lld",&x,&y);
C=k*x+b;
if(C>y){
scnt++;s[scnt].bh=i;
s[scnt].x=x;s[scnt].y=y;
}
else if(C==y){
rcnt++;r[rcnt].bh=i;
r[rcnt].x=x;r[rcnt].y=y;
}
else{
xcnt++;xia[xcnt].bh=i;
xia[xcnt].x=x;xia[xcnt].y=y;
}
}
while(scnt>0){
if(xcnt>0){
cnt++;
yes[cnt].x=xia[xcnt].bh;yes[cnt].y=s[scnt].bh;
scnt--;xcnt--;
}
else{
break;
}
}
while(rcnt>0){
if(xcnt>0){
cnt++;
yes[cnt].x=r[rcnt].bh;yes[cnt].y=xia[xcnt].bh;
rcnt--;xcnt--;
}
else if(scnt>0){
cnt++;
yes[cnt].x=r[rcnt].bh;yes[cnt].y=s[scnt].bh;
scnt--;rcnt--;
}
else{
cnt++;
yes[cnt].x=r[rcnt].bh;yes[cnt].y=r[rcnt-1].bh;
rcnt-=2;
}
}
while(scnt>0){
nocnt++;
no[nocnt].x=s[scnt].bh;no[nocnt].y=s[scnt-1].bh;
scnt-=2;
}
while(xcnt>0){
nocnt++;
no[nocnt].x=xia[xcnt].bh;no[nocnt].y=xia[xcnt-1].bh;
xcnt-=2;
}
cout<<cnt<<endl;
for(i=1;i<=cnt;i++){
printf("%lld %lld Y\n",yes[i].x,yes[i].y);
}
for(i=1;i<=nocnt;i++){
printf("%lld %lld N\n",no[i].x,no[i].y);
}
//fclose(stdin);fclose(stdout);
return 0;
}
E 小红的双好数（hard）
小想法：这题可以暴力枚举，通过枚举其中一个k-好数，然后check另外一个就OK了，观察发现，这题如果会超时，肯定是由于小数字导致的(<=5)。因为对于一个‘k-好数’，当k==2时，这无异于O(N)级别的枚举，会超时。
但是对于k1==2时，任何n对于‘k1-好数’都会满足题意。所以k==2，解决了。
我们暴力枚举肯定是优先从更大的k2去枚举，k2>k1，故k==3，解决了。
再C题我们可以知道，当k1==k2-1时，n==k2即为答案。故k1==3,k2==4，解决了。(其实当枚举k==4时，时间复杂度就可以优化到O(√N)了)
无奈的是还是会超时，我就自己跑完k==5的情况然后特判了，之后的时间复杂度就比较小了，没问题。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int k1,k2,n,ans=-1;
bool check(__int128 x,int k1,int k2){
while(x>0){
if((x%k1)>1)return false;
x/=k1;
}
return true;
}
void dfs(__int128 x){
if(ans!=-1)return;
if(x>1000000000000000000LL){
return;
}
if(x>=2&&check(x,k1,k2)==1){
ans=x;return;
}
else{
dfs(x*k2);dfs(x*k2+1);
}
}
signed main(){
//freopen("5.in","r",stdin);freopen("5.out","w",stdout);
cin>>k1>>k2;
if(k1==2){
cout<<"YES"<<endl;
cout<<k2<<endl;
}
else if(k1==k2-1){
cout<<"YES"<<endl;
cout<<k2<<endl;
}
else if(k1==3&&k2==5){
cout<<"YES"<<endl;
cout<<3250<<endl;
}
else{
dfs(1);
if(ans==-1)cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
cout<<ans<<endl;
}
}
//fclose(stdin);fclose(stdout);
return 0;
}
F 小红的数组操作
直接放了一个线段树板子上去，码风不好看，请见谅。
输入1 i j x将第i个数组的第j个元素修改为x；(单点修改)
输入2 i查询前i个数组的最小值。(1--sum[i]区间查询)
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
ll a[4000009],tree[4000009],i,n,m,op,x,y,k,q,bh[100009],j,num;
void build(ll node,ll start,ll end){
if(start==end){
tree[node]=a[start];//或return a[end]
}
else{//node是当前数在树中的坐标
ll mid=(start+end)/2;
ll zuo=2*node;//直接访问左子树
ll you=2*node+1;//直接访问右子树
build(zuo,start,mid);
build(you,mid+1,end);
tree[node]=min(tree[zuo],tree[you]);
}
}
void change(ll node,ll start,ll end,ll L,ll R,ll k){
if(end<L||start>R)return;//加速操作!!!
else if(start>=L&&end<=R){
tree[node]=k;
return;//记得return
}
else{
ll mid=(start+end)/2;
ll zuo=node*2;
ll you=node*2+1;
change(zuo,start,mid,L,R,k);
change(you,mid+1,end,L,R,k);
tree[node]=min(tree[zuo],tree[you]);
}
}
ll sum(ll node,ll start,ll end,ll L,ll R){
if(end<L||start>R)return 1000000009LL;//求最小值不要返回0！
else if(start>=L&&end<=R)return tree[node];
else{
ll mid=(start+end)/2;
ll zuo=2*node;
ll you=2*node+1;
ll x=sum(zuo,start,mid,L,R);
ll y=sum(you,mid+1,end,L,R);
return min(x,y);
}
}
signed main(){
//freopen("6.in","r",stdin);freopen("6.out","w",stdout);
cin>>n;
for(i=1;i<=n;i++){
scanf("%lld",&m);num+=m;
bh[i]=bh[i-1]+m;//用来记录到前i个数组有多少个数字
for(j=1;j<=m;j++){
scanf("%lld",&a[bh[i-1]+j]);
}
}
build(1,1,num);
cin>>q;
while(q--){
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&x,&y,&k);
int BH=bh[x-1]+y;
change(1,1,num,BH,BH,k);
}
else{
scanf("%lld",&x);
int BH=bh[x];
ll ans=sum(1,1,num,1,BH);
printf("%lld\n",ans);//1是根结点，就是sum[1,n]
}
}
//fclose(stdin);fclose(stdout);
return 0;
}
G 小红的双排列构造
小想法：把n一共分为三类。n<=2有可能出现无法构造的情况，n>=3就都OK了。
n=1：k==0与k==1构造不出来，k==2就是1 1即可。
n=2：k==0构造不出来，k==1,2,3单独特判。
n>=3:我们可以先考虑构造k==n+1的情况，然后再通过交换数组顺序减少排列数。k==n+1就是1 2...n 1 2...n这个情况。随后，我们考虑最后一个数字和第二组排列里面某一个数字交换，发现从第2*n开始，每选择向前一个数字交换，就会多破坏一组排列，如图所示，类似于一个长度为n的小滑块。这个方法还需要特判k=0与k=1。
k=0 构造 1 1 2 2 3 3...n n即可
k=1 构造 1 1 2 3...n n 2 3...n-1即可(使1重复两次，n重复两次即可)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,i,a[200009];
signed main(){
//freopen("7.in","r",stdin);freopen("7.out","w",stdout);
cin>>n>>k;
if(n==1){
if(k==2){
printf("1 1\n");
}
else printf("-1\n");
}
else if(n==2){
if(k==3){
printf("1 2 1 2\n");
}
else if(k==2){
printf("1 2 2 1\n");
}
else if(k==1){
printf("1 1 2 2\n");
}
else printf("-1\n");
}
else{
if(k==0){
for(i=1;i<=n;i++){
if(i==n)printf("%lld %lld\n",i,i);
else printf("%lld %lld ",i,i);
}
}
else if(k==1){
a[1]=1;a[n+2]=n;
for(i=2;i<=1+n;i++)a[i]=i-1;
for(i=n+3;i<=2*n;i++)a[i]=i-n-1;
for(i=1;i<=2*n;i++){
if(i==2*n)printf("%lld\n",a[i]);
else printf("%lld ",a[i]);
}
}
else{
for(i=1;i<=n;i++)a[i]=i,a[i+n]=i;
swap(a[2*n],a[2*n-(n+1-k)]);
for(i=1;i<=2*n;i++){
if(i==2*n)printf("%lld\n",a[i]);
else printf("%lld ",a[i]);
}
}
}
//fclose(stdin);fclose(stdout);
return 0;
}
感谢各位的观看，欢迎指正。
京公网安备 11010502036488号