B. Coffee Chicken
大致题意：
- S(1)="COFFEE";
- S(2)="CHICKEN";
- S(n)=S(n-2):S(n-1)----即第n-2个字符串作为前缀，第n-1个字符串作为后缀.
T组询问,求第n个字符串中第k个位置的字符.(1<=T<=1000,1<=n<=500,k<=min{ |S(n)|,1e12} )
分析:
- 我们可以处理出长度<=1e12的字符串一共57个
- 我们可以直接对长度进行dfs分治求pos位置.需要注意的是n>56时，前缀字符串跟n的奇偶性有关.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[502];
string s[3];
void dfs( ll x,ll k,ll r )
{
if( x<=2 )
{
for( int i=k-1;i<min(r,(ll)s[x].size());i++ ) cout<<s[x][i];
return ;
}
if( r<=(ll)a[x-2] ) dfs(x-2,k,r);
else if( k<=a[x-2] && r>a[x-2] )
{
dfs(x-2,k,a[x-2]);
dfs(x-1,1,r-a[x-2]);
}
else
{
k-=a[x-2];
dfs(x-1,k,r-a[x-2]);
}
}
int main()
{
s[1]="COFFEE";s[2]="CHICKEN";
a[1]=6,a[2]=7;
for( int i=3;i<=57;i++ ) a[i]=a[i-1]+a[i-2];
int t;
scanf("%d",&t);
while( t-- )
{
ll n,k;
scanf("%lld%lld",&n,&k);
if( n>56 )
{
if( n%2==0 ) n=56;
else n=57;
}
dfs(n,k,k+9);
puts("");
}
}C. Gifted Composer
大致题意：七个音符{do re mi fa sol la si},有一个空序列,n次操作,每次操作在序列头部或尾部插入一个音符,问每次操作有多少种循环节.----循环节定义 能划分成k个重复的部分 后面允许跟着一个不完整的部分(完整部分的初始部分)
分析：对字符串进行哈希处理，记录每次操作对应字符串S的区间[L,R],枚举循环节长度为i，二分找到符合字符串的最后出现的操作pos,那么长度i的循环节的贡献[i,pos],利用差分统计答案即可.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
using namespace std;
char s[10],t[maxn],ss[10];
int L[maxn],R[maxn];
int a[maxn];
struct Hash{
ll p[maxn],hash[maxn],base=131;
ll getHash(int l,int r )
{
ll ans=(hash[r]-hash[l-1]*p[r-l+1])%mod;
return (ans+mod)%mod;
}
void init( char *buf )
{
int n=strlen(buf);
p[0]=1;
for( int i=1;i<=n;i++ ) p[i]=p[i-1]*base%mod;
for( int i=1;i<=n;i++ )
{
hash[i]=( hash[i-1]*base%mod+(buf[i-1]-'a'+1) )%mod;
}
}
}hh;
int check( int q,int x )
{
return ( hh.getHash(L[q],R[q]-x)==hh.getHash(L[q]+x,R[q]) );
}
int main()
{
int n,head=1e6+1,tail=1e6+2;
scanf("%d",&n);
for( int i=1;i<=n;i++ )
{
scanf("%s%s",ss,s);
char c=s[0];
if( c=='s' && s[1]=='i' ) c='z';
if( ss[0]=='a' ) t[tail++]=c;
else t[head--]=c;
L[i]=head+1,R[i]=tail-1;
}
for( int i=1;i<=n;i++ ) L[i]-=head,R[i]-=head;
t[tail]=0;
hh.init(t+head+1);
for( int i=1;i<=n;i++ )
{
int l=i,r=n;
while( l<=r )
{
int mid=(l+r)>>1;
if( check(mid,i) ) l=mid+1;
else r=mid-1;
}
a[i]++,a[r+1]--;
}
for( int i=1;i<=n;i++ )
{
a[i]+=a[i-1];
printf("%d\n",a[i]);
}
return 0;
} D. Han Xin and His Troops
大致题意：给定n个( x=b( mod a ) )同余方程，求最小的x满足所有方程.(n<=100,m<=1e18,0<b<a<1e5 )
分析：两种解法.
- 1.套用CRT板子-----注意爆longlong 要用__int128
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
typedef __int128 ll;
ll m[maxn];
ll a[maxn];
ll m1;
void read(ll &x )
{
x=0;int f=1;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
x*=f;
}
inline void print( ll x )
{
if( x<0 )
{
x=-x;
putchar('-');
}
if( x>9 ) print(x/10);
putchar( x%10+'0' );
}
struct node{
ll exgcd( ll a1,ll b,ll &x,ll &y )
{
if( b==0 )
{
x=1;y=0;
return a1;
}
exgcd(b,a1%b,x,y);
ll r=exgcd( b,a1%b,y,x );
y-=x*(a1/b);
return r;
}
ll solve( ll *a,ll *m,ll n )
{
ll c=a[0],l=m[0];
ll d,x,y;
for(int i=1;i<n;i++ )
{
d=exgcd( l,m[i],x,y );
if( ( a[i]-c)%d ) return -1;
x=( a[i]-c )/d*x%( m[i]/d );
c+=l*x;
l=l/d*m[i];
c%=l;
}
return c >= 0 ? c : c+l;
}
}CRT;
int main()
{
ll n;
read(n);read(m1);
for( int i=0;i<n;i++ )
{
read(m[i]);
read(a[i]);
}
ll ans=CRT.solve(a,m,n);
if( ans==-1 ) printf("he was definitely lying\n");
else if( ans>m1 ) printf("he was probably lying\n");
else print(ans);
}- 2.出题人推荐的方法.利用LCM(p1,p2...p-1)=y, 在有解的情况下满足pi同余式，ans+=y,可以证明加的次数不超过pi次.并且该方法不会爆long long. ( 有解判定,n个模数是否互质 ).-------该方法只适用于模数较小情况.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[105],b[105];
ll n,m;
void solve()
{
ll ans=b[1];
ll tmp=a[1];
for( int i=1;i<=n;i++ )
{
for( int j=1;j<=i;j++ )
{
int gd=__gcd(a[i],a[j]);
if( b[i]%gd!=b[j]%gd )
{
puts("he was definitely lying");
return;
}
}
}
for( int i=2;i<=n;i++ )
{
for( int j=0;j<a[i] && ans<=m && ans%a[i]!=b[i] ;j++ ) ans+=tmp;
if( ans>m )
{
puts("he was probably lying");
return;
}
tmp=tmp/__gcd(tmp,a[i])*a[i];
}
printf("%lld\n",ans);
}
int main()
{
scanf("%lld%lld",&n,&m);
for( int i=1;i<=n;i++ ) scanf("%lld%lld",&a[i],&b[i]);
solve();
}F. Popping Balloons
大致题意:给定n*n的矩阵，有n个气球分布在矩阵中,我们横着打三枪，竖着打三枪，打枪 横/竖 间隔为r.求最多能打掉多少气球.
分析：该题目有三种方法.
1.出题人解法.-----暂无标程
暴力枚举横向打法.我们考虑打x1,x1+r,x1+2 * r 三枪,用g(i)表示i列气球个数和.横向打枪的打中气球(x,y)，会影响列向气球个数.那么我们可以用一个muliset维护列向气球个数.对于横向每一个方案，对于影响的列向气球个数进行log(n)取出修改插入.我们可以计算每个气球的操作次数为9log(n) .那么该方案的复杂度为O(9n*log(n) )
2.解法二
我们处理出所有横向打法的方案贡献并排序.最终答案肯定出现在最大的几个方案中，那么我们可以暴力计算最大的100个方案，进行更新即可。(实测只需要暴力计算最大的4..5个方案)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,r,fx[maxn*3],fy[maxn*3],res;
struct node{
int x,y;
}a[maxn],w[maxn];
bool cmp( node xx,node yy )
{
return xx.x>yy.x;
}
int main()
{
cin>>n>>r;
memset(fx,0,sizeof(fx));
for( int i=0;i<n;i++ )
{
cin>>a[i].x>>a[i].y;
fx[a[i].x]++;
}
for( int i=0;i<maxn;i++ )
{
w[i].x=fx[i]+fx[i+r]+fx[i+2*r];
w[i].y=i;
}
sort(w,w+maxn,cmp);
for( int i=0;i<=4;i++ )
{
memset(fy,0,sizeof(fy));
for( int j=0;j<n;j++ )
{
if( a[j].x!=w[i].y && a[j].x!=w[i].y+r && a[j].x!=w[i].y+2*r )
{
fy[a[j].y]++;
}
}
int my=0;
for( int j=0;j<maxn;j++ ) my=max( my,fy[j]+fy[j+r]+fy[j+2*r] );
res=max(res,my+w[i].x);
}
cout<<res<<endl;
}3.解法三----rank1 杜大佬的方法 复杂度O(n) 暂时没搞懂.......鸽了.....
G.Road Construction
大致题意:给定n个点的坐标，请画一条直线满足(n<=300,xi,yi<=1e9)
- 将点均分成两部分。
- 并且直线上不过点
- 使得所有点到直线的距离的最小值 最大.
分析：我们可以得到结论----满足直线一定是平行某两个点的连线或者是某两点连线的中垂线。(简单证明即可).
n不超过300,然后我们枚举所有的斜率，把所有点按斜率排序，取中间两个点，让这两个点到直线距离相等，这个距离就是当前的最小距离。然后求最小距离最大值。复杂度O(n^3*logn)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=302;
struct node{
double x,y,b;
bool operator < ( const node &t )const{
return b<t.b;
}
}p[maxn];
double x[maxn],y[maxn];
double dis( double k,double b,double x,double y )
{
return fabs(k*x+b-y)/sqrt(k*k+1.0);
}
int main()
{
int n;
scanf("%d",&n);
for( int i=1;i<=n;i++ )
{
scanf("%lf%lf",&x[i],&y[i]);
p[i].x=x[i];
p[i].y=y[i];
}
double ans=0;
for( int i=1;i<=n;i++ )
{
for( int j=i+1;j<=n;j++ )
{
double k=(y[i]-y[j])/(x[i]-x[j]); // 平行的情况
for( int l=1;l<=n;l++ )
{
p[l].b=p[l].y-k*p[l].x;
}
sort(p+1,p+1+n);
double b=(p[n/2].b+p[n/2+1].b)/2;
ans=max( ans,dis(k,b,p[n/2].x,p[n/2].y) );
k=-1.0/k; // 垂直的情况
for( int l=1;l<=n;l++ )
{
p[l].b=p[l].y-k*p[l].x;
}
sort(p+1,p+1+n);
b=(p[n/2].b+p[n/2+1].b)/2;
ans=max( ans,dis(k,b,p[n/2].x,p[n/2].y) );
}
}
printf("%.10lf\n",ans);
return 0;
} ---nth_element可以将复杂度降至O(n^3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=302;
double x[maxn],y[maxn],b[maxn],ans;
int n;
void solve( double k )
{
for( int i=0;i<n;i++ ) b[i]=y[i]-k*x[i];
nth_element(b,b+n/2,b+n);
double d1=b[n/2];
double d2=*max_element(b,b+n/2);
double w=(d1-d2)/sqrt(1+k*k);
ans=max(ans,w/2);
}
int main()
{
scanf("%d",&n);
for( int i=0;i<n;i++ ) scanf("%lf%lf",&x[i],&y[i]);
for( int i=0;i<n;i++ )
{
for( int j=i+1;j<n;j++ )
{
double k=(y[i]-y[j])/(x[i]-x[j]);
solve(k);
solve(-1.0/k);
}
}
printf("%.12lf\n",ans);
return 0;
} H.Stammering Chemists
大致题意：给定6个点，5条边.判断该图形结构.
分析：按点的度判断即可.
#include<bits/stdc++.h>
using namespace std;
// 1 2 3 4
// 2 4 n-hexane
// 3 2 1 2-methylpentane
// 3 2 1 3-methylpentane
// 4 0 2 2,3-dimethylbutane
// 4 2 0 1 2,2-dimethylbutane
vector<int>g[10];
int ans=0;
void dfs( int x,int f ,int dep )
{
ans=max(ans,dep);
for( auto v:g[x] )
{
if( v==f ) continue;
dfs(v,x,dep+1);
}
}
int main()
{
int t;
cin>>t;
while( t-- )
{
ans=0;
int vis[5]={0};
for( int i=1;i<=6;i++ ) g[i].clear();
for( int i=1;i<6;i++ )
{
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for( int i=1;i<=6;i++ ) vis[ g[i].size() ]++;
if( vis[1]+vis[2]==6 ) puts("n-hexane");
else if( vis[1]+vis[3]==6 ) puts("2,3-dimethylbutane");
else if( vis[1]+vis[2]+vis[4]==6 ) puts("2,2-dimethylbutane");
else
{
int s;
for( int i=1;i<=6;i++ ) if( g[i].size()==3 ) s=i;
dfs(s,0,0);
if( ans==2 ) puts("3-methylpentane");
else puts("2-methylpentane");
}
}
}
京公网安备 11010502036488号