D
暴力打表找规律。。。
#include <cstdio>
#include <cstring>
using namespace std;
int i,j,k,n,m,x,y,t;
int a[210];
int ans[200010];
void work1(int num){
x=(n)/2+1;
for (i=1;i<=x-1;i++)printf("b");printf("r");for (i=x+1;i<=n;i++)printf("b");printf("\n");num--;
if (n%2==0){
x=(n)/2;
for (i=1;i<x;i++)printf("b");printf("r");for (i=x+1;i<=n;i++)printf("b");printf("\n");num--;
}
x=(n)/2;
for (i=1;i<x;i++)printf("b");printf("r");for (i=x+1;i<n;i++)printf("b");printf("r\n");num--;
for (i=1;i<x;i++)ans[i]='b';ans[x]='r';for (i=x+1;i<=n;i++)ans[i]='b';ans[n-1]=ans[n]='r';
y=n-2;
for (int T=1;T<=num;T++){
for (i=1;i<=n;i++)printf("%c",ans[i]);printf("\n");
ans[y]='r';ans[y+2]='b';y--;
}
}
void work2(){
int num=0;y=((n+1)/2)*(n+1-(n+1)/2);
for (int P=0;P<(1ll<<n);P++){
x=P;for (i=n;i>=1;i--)a[i]=x&1,x>>=1;
t=0;
for (i=1;i<=n;i++){
k=0;
for (j=i;j<=n;j++){
k+=a[j];
if (k&1)t++;
}
}
if (t==y){
for (i=1;i<=n;i++)
if (!a[i])printf("b");else printf("r");printf("\n");
num++;
if (num>=100)return ;
}
}
}
int main(){
scanf("%d",&n);long long y=1ll*((n+1)/2)*(n+1-(n+1)/2);
printf("%lld\n",y);
if (n>=196){
work1(100);
return 0;
}
else if (n<=30){
work2();
return 0;
}
if (n>30){
work1(n/2+2);
y=((n+1)/2)*(n+1-(n+1)/2);
int num=n/2+2;
memset(a,0,sizeof a);
for (int P=0;P<(1<<15);P++){
x=P;for (i=n;i>=(n-14);i--)a[i]=x&1,x>>=1;
a[n/2-1]=1;
t=0;
for (i=1;i<=n;i++){
k=0;
for (j=i;j<=n;j++){
k+=a[j];
if (k&1)t++;
}
}
// for (i=1;i<=n;i++)if (!a[i])printf("b");else printf("r");printf("\n");
// printf("%d %d\n",t,y);
// num++;
// if (num>=100)return 0;
if (t==y){
for (i=1;i<=n;i++)
if (!a[i])printf("b");else printf("r");printf("\n");
num++;
if (num>=100)return 0;
}
}
}
}F
简单的贪心
#include <bits/stdc++.h>
using namespace std;
int i,j,k,n,m,x,y,t;
int a[1000100],s1[1000010],s2[1000010],s3[1000100];
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++)scanf("%d",&a[i]),s3[i]=max(s3[i-1],a[i]);
s1[n+1]=1000000001;s2[n+1]=n+1;s3[n+1]=0;
for (i=n;i>=1;i--){
if (a[i]<=s1[i+1]){
s1[i]=a[i];
s2[i]=i;
}
else{
s1[i]=s1[i+1];
s2[i]=s2[i+1];
}
}
int ans=0;x=1;
while (x<=n){
y=s2[x];
while (s1[y+1]<s3[y])y++;
ans++;x=y+1;
}
printf("%d\n",ans);
}
G
简单的背包问题
#include <bits/stdc++.h>
using namespace std;
long long f[1010][1010];
int a[1010],n,k,i,j;
int main(){
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=1;i<=n;i++){
for (j=0;j<=k;j++)f[i][j]=f[i-1][j];
for (j=1;j<=k;j++)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);
}
printf("%lld\n",f[n][k]);
}
I
照理说是类欧。。
但我乱整也给整出来了
#include <bits/stdc++.h>
using namespace std;
int i,j,k,n,m,x,y,t,H,M;
long long A,T,dh,Tm;
int Try(int t){
return 1ll*t*dh%(H-1)==0;
}
int findcir(int x){
for (int i=1;i<=sqrt(x);i++)
if (x%i==0){
if (Try(i))return i;
}
for (int i=sqrt(x);i>=1;i--)
if (x%i==0){
if (Try(x/i))return x/i;
}
}
long long gcd(long long x,long long y){
return y==0?x:gcd(y,x%y);
}
int main(){
scanf("%d%d%lld",&H,&M,&A);
if (A==1ll*H*M/2&&(1ll*H*M%2==0)){
printf("%lld\n",1ll*H*M);
return 0;
}
if (A==0){
printf("%d\n",gcd(H-1,M));
return 0;
}
T=A/(H-1),dh=1ll*H*M%(H-1),Tm=A%(H-1);
long long ans=2ll*T*(H-1);
if (A%(H-1)==0){
printf("%lld\n",ans+1);
return 0;
}
if (dh==0){
printf("%lld\n",1ll*(H-1)*(1+2*(A/(H-1))));
return 0;
}
int cir=findcir(H-1);
// printf("%d\n",cir);
long long g=gcd(dh,H-1);
long long C=(H-1-Tm);
long long fi=((C-1)/g+1)*g;
// printf("%lld %lld\n",C,fi);
ans+=1ll*((H-fi-2)/g+1)*((H-1)/cir);
ans+=1ll*(Tm/g)*((H-1)/cir);
printf("%lld\n",ans+(H-1)/cir);
return 0;
}
Comments | NOTHING