本场总结:
A.模拟暴力
B.猜结论
C.贪心
D.签到
E.离散化+树状数组+二分 ----插入区间元素找中位数
H.数位dp
J.签到
小结:
----多项式可约问题，三次多项式实数范围内可约.二次多项式根判别式.
----注意数据范围再贪心，一般比较小的值作为索引进行贪心.
----插入区间元素可以用两个树状数组维护，查找中位数一般就是二分
----练习数位dp
A. String
大致题意:给定一个01串，请把它划分为尽量少的子串，每个子串是该子串循环移位的字典序最小的串.
分析：暴力找就行，check判断.
#include<bits/stdc++.h>
using namespace std;
bool check( string s )
{
int n=s.size();
for( int i=1;i<n;i++ )
{
for( int j=0;j<n;j++ ) // 自循环就是依次让每个数字都做一次最高位
{
if( s[j]<s[(i+j)%n] ) break;
if( s[j]>s[(i+j)%n] ) return false;
}
}
return true;
}
int main()
{
int t;
cin>>t;
while( t-- )
{
string a;
cin>>a;
int i=0;
int n=a.size();
while( i<n )
{
for( int j=n-i;j>0;j-- )
{
if( check( a.substr(i,j) ) )
{
cout<<a.substr(i,j);
i+=j;
if( i<n ) cout<<" ";
break;
}
}
}
cout<<endl;
}
return 0;
}B. Irreducible Polynomial
大致题意：给定一个多项式，判断在实数范围内是否可约.提取常数项不算可约.
分析：有一个结论，对于实数范围内n>=3次方的多项式必然可约，而n==2只需判断根判别式.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while( t-- )
{
int n;
cin>>n;
int a,b,c;
if( n<=1 )
{
for( int i=0;i<=n;i++ )cin>>a;
puts("Yes");
}
else if( n==2 )
{
cin>>a>>b>>c;
if( 1ll*b*b<4ll*a*c ) puts("Yes");
else puts("No");
}
else
{
for( int i=0;i<=n;i++ )cin>>a;
puts("No");
}
}
}C. Governing sand
大致题意:有很多树，每棵树不同种类砍掉花费也不同，高度也不同，现要砍掉一些树让最高的树的数量是所有树的数量之和的一半以上，请计算最小花费.
分析：每颗数的花费是<=200的，那么我们可以先按树的高度进行排序，然后使当前树为最高的高度去计算花费，对于之前的树开一个200空间的数组按花费维护即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n;
ll sum,maxx,g[205];
struct node{
ll h,p,c;
}t[maxn];
bool cmp( node x,node y )
{
return x.h<y.h;
}
int main()
{
while( ~scanf("%d",&n) )
{
sum=0;
for( int i=1;i<=n;i++ )
{
scanf("%lld%lld%lld",&t[i].h,&t[i].c,&t[i].p);
sum+=t[i].p*t[i].c; // 所有树全砍掉 的花费
}
sort(t+1,t+1+n,cmp);
maxx=t[1].c*t[1].p;
for( int i=1;i<=200;i++ ) g[i]=0;
int tot=0;
ll fsum=0,max1=0;
for( int i=1;i<=n;i++ )
{ // 选定当前高度的树为最高
fsum+=t[i].p; // ----- 树的数量
max1+=t[i].c*t[i].p; // 树的价值
if( i==n || t[i].h!=t[i+1].h )
{
fsum--;
for( int j=200;j>=1;j-- )
{
if( fsum<=g[j] )
{
max1+=j*fsum;
break;
}
else
{
max1+=j*g[j];
fsum-=g[j];
}
}
maxx=max(max1,maxx);
fsum=0,max1=0;
while( tot<i )
{
tot++;
g[t[tot].c]+=t[tot].p;
}
}
}
printf("%lld\n",sum-maxx);
}
} D. Number
大致题意:给定一个质数p,请找一个n位数能够整除p.
分析:签到题.n<p的位数 则为没有,n>=p的位数,输出p，后面位数补0即可.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
string p;
cin>>n>>p;
if( n==p.size() ) cout<<p;
else if( n>p.size() )
{
cout<<p;
for( int i=0;i<n-p.size();i++ ) cout<<"0";
}
else cout<<"T_T";
}E.Find the median
大致题意:开始一个空序列，n次操作，每次插入[li,ri]区间的数.然后输出序列的中位数的值.li,ri的给定计算公式.
分析:我们要记录序列个数和序列元素，题意是按区间插入元素，那么我们可以利用差分的思想，在l位置插入-l,在r的位置插入r+1,用一个树状数组去维护，那么前缀和即使当前序列的元素个数.那么中位数怎么找呢。要运用二分的思想去check中位数,对于当前中位数假如它在一段l-r区间数里面，如何计算[l,pos]个数呢。我们可以再用一个树状数组来标记.插入[li,ri]区间的数,在li位置标记+1,ri位置标记-1，计算前缀和，如果前缀和大于0的话那么肯定在某一段或者多段区间里面，那么少了右端点，但对于当前check右端点就是mid，所以加上缺失右端点的左端点个数*(mid+1)就能计算个数了.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+10;
int x[maxn],y[maxn],l[maxn],r[maxn];
int num[maxn<<1],cnt,n;
ll sum1[maxn<<2],sum2[maxn<<2];
int lowbit(int x ) { return x&(-x); }
void add( ll a[],int x,int C ) { while( x<=cnt ) a[x]+=C,x+=lowbit(x); }
ll query( ll a[],int x ) { ll ans=0; while( x ) ans+=a[x],x-=lowbit(x); return ans; }
void init()
{
ll a1,b1,a2,b2,m1,m2,c1,c2;
scanf("%d",&n);
scanf("%d%d%lld%lld%lld%lld",&x[1],&x[2],&a1,&b1,&c1,&m1);
scanf("%d%d%lld%lld%lld%lld",&y[1],&y[2],&a2,&b2,&c2,&m2);
for( int i=1;i<=n;i++ )
{
if( i>2 ) x[i]=( a1*x[i-1]+b1*x[i-2]+c1 )%m1;
if( i>2 ) y[i]=( a2*y[i-1]+b2*y[i-2]+c2 )%m2;
l[i]=min( x[i],y[i] )+1;
r[i]=max( x[i],y[i] )+1;
num[++cnt]=l[i];
num[++cnt]=r[i]+1;
}
sort(num+1,num+1+cnt);
cnt=unique(num+1,num+cnt+1)-num-1;
}
int get_id( int x ) { return lower_bound(num+1,num+cnt+1,x)-num; }
void solve()
{
ll all=0;
for( int i=1;i<=n;i++ )
{
all+=r[i]-l[i]+1;
int L=get_id(l[i]);
int R=get_id(r[i]+1);
add(sum1,L,-l[i]);add(sum1,R,r[i]+1);
add(sum2,L,1); add(sum2,R,-1);
L=1,R=1e9;
while( L<R )
{
int mid=(L+R)/2;
int pos=upper_bound(num+1,num+1+cnt,mid)-num-1;
ll tmp=query(sum1,pos)+query(sum2,pos)*(mid+1);
if( tmp<(all+1)/2 ) L=mid+1;
else R=mid;
}
printf("%d\n",L);
}
}
int main()
{
init();
solve();
} H.Pair
大致题意:给定三个数字a,b,c，找无序对(x,y)满足 x^y<c 或者 (x&y)<c 的个数. ( 1<=x<=a, 1<=y<=b )
分析:显然是一道数位dp的题.坑点就是要减去 x==0 和 y==0的情况.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int bita[50],bitb[50],bitc[50];
ll dp[50][2][2][2][2];
ll dfs( int len,int ma,int mb,int ad,int xo )
{
if( !len ) return 1;
if( dp[len][ma][mb][ad][xo]>=0 ) return dp[len][ma][mb][ad][xo];
ll ans=0;
int upa=ma ? bita[len] : 1;
int upb=mb ? bitb[len] : 1;
for( int i=0;i<=upa;i++ )
{
for( int j=0;j<=upb;j++ )
{
if( ad && (i & j)>bitc[len] || xo && ( i^j )<bitc[len] ) continue;
ans+=dfs(len-1,ma && ( i==upa ), mb && ( j==upb ),
ad && ( (i & j)==bitc[len] ),xo && ( ( i^j )==bitc[len] ) );
}
}
dp[len][ma][mb][ad][xo]=ans;
return ans;
}
ll solve( ll a,ll b,ll c )
{
int num1=0,num2=0,num3=0;
while( a ) { bita[++num1]= a&1 ;a>>=1; }
while( b ) { bitb[++num2]= b&1 ;b>>=1; }
while( c ) { bitc[++num3]= c&1 ;c>>=1; }
int len=max( num1,max(num2,num3) );
return dfs(len,1,1,1,1);
}
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
memset(dp,-1,sizeof(dp));
memset(bita,0,sizeof(bita));
memset(bitb,0,sizeof(bitb));
memset(bitc,0,sizeof(bitc));
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
ll ans=solve(a,b,c);
ans-=max(0ll,a-c+1);
ans-=max(0ll,b-c+1);
printf("%lld\n",a*b-ans);
}
}J. A+B problem
大致题意:给定a,b两个数。求a的逆序数加上b的逆序数的和的逆序数.
分许:签到题,模拟即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll rev( ll x )
{
ll ans=0,cnt=0;
while( x )
{
ans*=10;
ans+=x%10;
x/=10;
}
return ans;
}
int main()
{
int t;
cin>>t;
while( t-- )
{
ll a,b;
cin>>a>>b;
cout<<rev(rev(a)+rev(b))<<endl;
}
}
京公网安备 11010502036488号