2019 牛客多校第七场

String

64bit IO Format: %lld

题目描述

A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations.
For example: "0101" is perfect as it is the smallest string among ("0101", "1010", "0101", "1010").

Given a 01 string, you need to split it into the least parts and all parts are perfect.

输入描述:

The first line of the input gives the number of test cases, T (T≤300)T\ (T \leq 300)T (T≤300).  test cases follow.

For each test case, the only line contains one non-empty 01 string. The length of string is not exceed 200.

输出描述:

For each test case, output one string separated by a space.

4
0
0001
0010
111011110

0
0001
001 0
111 01111 0

签到，把0000001111111这种分段，判断相邻两段能不能合并。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+10;
string s,pre;
vector<string> v;
int len;
void work(){
v.clear();
string a;
int fl=1;
rep(i,0,len-1){
if(s[i]=='1') a+=s[i],fl=0;
else if(s[i]=='0'){
if(fl) a+=s[i];
else{
v.pb(a); a=s[i]; fl=1;
}
}
if(i==len-1) v.pb(a);
}
}
void solve(){
cin>>s;
len=s.length();
int fr=1;
work();
int num=v.size(),pos1=0,pos2=1;
if(num==1) cout<<v[0]<<endl;
else{
while(1){
string a=v[pos1],b=v[pos2];
int a1=0,a2=0,b1=0,b2=0;
string t=b+a,tt=a+b;
if(tt<=t){
v[pos1]+=v[pos2]; pos2++;
}
else{
if(fr) cout<<a;
else cout<<" "<<a;
fr=0;
v[pos1]=v[pos2];
pos2++;
}
if(pos2==num){
if(fr) cout<<v[pos1];
else cout<<" "<<v[pos1];
fr=0;
break;
}
}
puts("");
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}

Irreducible Polynomial

64bit IO Format: %lld

题目描述

In mathematics, a polynomial is an expression consisting of variables (also called indeterminate) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. For example, x2+4x+7x^2 + 4x + 7x2+4x+7.

A polynomial is said to be irreducible if it cannot be factored into two or more non-trivial polynomials with real coefficients.
For example, x2+1x^2+1x2+1 is irreducible, but x2−2x+1x^2-2x+1x2−2x+1 is not (since x2−2x+1=(x−1)(x−1)x^2-2x+1=(x-1)(x-1)x2−2x+1=(x−1)(x−1)).

Given a polynomial of degree

with integer coefficients: anxn+an−1xn−1+...+a1x+a0a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0an​xn+an−1​xn−1+...+a1​x+a0​, you need to check whether it is irreducible or not.

输入描述:

The first line of the input gives the number of test cases, T (T≤100)T\ (T \leq 100)T (T≤100).  test cases follow.

For each test case, the first line contains one integers n (0≤n≤20)n\ (0 \leq n \leq 20)n (0≤n≤20). Next line contains n + 1n\ +\ 1n + 1 integer numbers:
an,an−1,...,a1,a0a_n, a_{n-1}, ..., a_1, a_0an​,an−1​,...,a1​,a0​

−109≤ai≤109-10^9 \leq a_i \leq 10^9−109≤ai​≤109

an≠0a_n \ne 0an​​=0

输出描述:

For each test case, output "Yes" if it is irreducible, otherwise "No".

2
2
1 -2 1
2
1 0 1

No
Yes

实数域不可拆分多项式只有两种：一次多项式和二次的(b^2<4ac)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int cnt=0;
for(int i=0;i<=n;i++){
if(a[i]==0) cnt++;
scanf("%lld",&a[i]);
}
if(n>2){
printf("No\n");
}
else if(n==0 || n==1){
printf("Yes\n");
}
else{
ll x=a[1]*a[1]-a[0]*a[2]*4;
if(x<0){
printf("Yes\n");
}
else{
printf("No\n");
}

}
}
return 0;
}

Governing sand

64bit IO Format: %lld

题目描述

The Wow village is often hit by wind and sand,the sandstorm seriously hindered the economic development of the Wow village.
There is a forest in front of the Wowo village, this forest can prevent the invasion of wind and sand. But there is a rule that the number of tallest trees in the forest should be more than half of all trees, so that it can prevent the invasion of wind and sand. Cutting down a tree need to cost a certain amount of money. Different kinds of trees cost different amounts of money. Wow village is also poor. There are n kinds of trees. The number of i-th kind of trees is PiP_iPi​, the height of i-th kind of trees is HiH_iHi​, the cost of cutting down one i-th kind of trees is CiC_iCi​.
(Note: "cutting down a tree" means removing the tree from the forest, you can not cut the tree into another height.)

输入描述:

The problem is multiple inputs (no more than 30 groups).
For each test case.
The first line contines one positive integers n(1≤n≤105)n (1 \leq n \leq 10^5)n(1≤n≤105),the kinds of trees.
Then followed n lines with each line three integers Hi(1≤Hi≤109)H_i (1 \leq H_i \leq 10^9)Hi​(1≤Hi​≤109)-the height of each tree, Ci(1≤Ci≤200)C_i (1 \leq C_i \leq 200)Ci​(1≤Ci​≤200)-the cost of cutting down each tree, and Pi(1≤Pi≤109)P_i(1 \leq P_i\leq 10^9)Pi​(1≤Pi​≤109)-the number of the tree.

输出描述:

For each test case, you should output the minimum cost.

2
5 1 1
1 10 1
2
5 1 2
3 2 3

1
2

从从低到高枚举最高的树，在剩下的树当中砍掉代价最小的。可以用一颗线段树维护。线段树按照代价从小到大的顺序构建，支持加入类树，查询前x个的总和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int lowbit(int x){
return x&(-x);
}
struct node{
ll h,c,p;
bool operator < (const node& y){
return h<y.h;
}
};
node a[100100];
ll num[250],val[250];
void ins(int pos,ll v,ll c[]){
for(int i=pos;i<250;i+=lowbit(i)){
c[i]+=v;
}
return;
}
ll que(int pos,ll c[]){
ll ret=0;
for(int i=pos;i>0;i-=lowbit(i)){
ret+=c[i];
}
return ret;
}
ll suf[100100];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(num,0,sizeof(num));memset(val,0,sizeof(val));
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&a[i].h,&a[i].c,&a[i].p);
}
sort(a+1,a+1+n);
suf[n+1]=0;
suf[n]=a[n].c*a[n].p;
for(int i=n-1;i>=1;i--){
suf[i]=suf[i+1]+a[i].c*a[i].p;
}
int pre=1;ll su=0;ll cnt=0;ll aans=100000000000000000;
for(int i=1;i<=n;){
int ppt=i;
for(int j=i+1;j<=n;j++){
if(a[j].h!=a[i].h){
break;
}
ppt=j;
}
for(int j=i;j<=ppt;j++){
cnt+=a[j].p;
su+=a[j].p;
}
ll cos=suf[ppt+1];
if(cnt>su/2){
aans=min(aans,cos);
}
else{
ll tar=su-2*cnt+1;
int lb=1,ub=200,ans=0;
while(lb<=ub){
int md=(lb+ub)>>1;
ll tmp=que(md,num);
if(tmp>=tar){
ans=md;
ub=md-1;
}
else{
lb=md+1;
}
}
if(ans-1>0){
assert(ans<=200);
cos+=que(ans-1,val);
cos+=(ans*(tar-que(ans-1,num)));
aans=min(cos,aans);
}
else{
cos+=(ans*(tar-que(ans-1,num)));
aans=min(cos,aans);
}
}
cnt=0;

for(int j=i;j<=ppt;j++){
ins(a[j].c,a[j].p,num);
ins(a[j].c,a[j].p*a[j].c,val);
}
i=ppt+1;
}
printf("%lld\n",aans);
}
return 0;
}

Number

Special Judge, 64bit IO Format: %lld

题目描述

I have a very simple problem for you. Given a positive integeter n (1≤n≤1000000)n\ (1 \leq n \leq 1000000)n (1≤n≤1000000) and a prime number p (2≤p≤1000000)p\ (2 \leq p \leq 1000000)p (2≤p≤1000000), your job is to output a positive number which is divisible by

and has exactly

digits. Please output "T_T" if you can not find such number.

输入描述:

The first line of the input file contains two integers n (1≤n≤1000000)n\ (1 \leq n \leq 1000000)n (1≤n≤1000000) and p (2≤p≤1000000)p\ (2 \leq p \leq 1000000)p (2≤p≤1000000). is a prime number.

输出描述:

Output one number (without leading zeros) or "T_T"

2 5

10

1 11

T_T

5 2

10000

签到题。If len(p) > n: 无解If len(p) = n: 输出pIf len(p) < n: 先输出p, 然后补上0

#include<iostream>
#include<cstdio>

using namespace std;

int z,x,n,m,w,h;

int main()
{
scanf("%d%d",&z,&x);

n=x;m=0;
while(n)
{
n=n/10;m++;
}

if (z<m) printf("T_T\n");
else
{
printf("%d",x);
for (int i=1;i<=z-m;i++)
printf("0");
}

return 0;
}

Pair

64bit IO Format: %lld

题目描述

Given three integers

,

,

. Count the number of pairs <x ,yx\ , yx ,y> (with 1≤x≤A1 \leq x \leq A1≤x≤A and 1≤y≤B1 \leq y \leq B1≤y≤B)
such that at least one of the following is true:
- (x and yx\ and\ yx and y) >

- (x xor yx\ xor\ yx xor y) <

("and", "xor" are bit operators)

输入描述:

The first line of the input gives the number of test cases, T (T≤100)T\ (T \leq 100)T (T≤100).  test cases follow.

For each test case, the only line contains three integers , and .
1≤A,B,C≤1091 \leq A,B,C \leq 10^91≤A,B,C≤109

输出描述:

For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

3
3 4 2
4 5 2
7 8 5

5
7
31

数位DP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[31][2][2][3][3];
ll a,b,c;
int aa[39];
int bb[39];
ll dfs(int pos,int lima,int limb,int g,int l){
if(pos==-1){
if(g!=1 && l!=1) return 0;
return 1;
}
if(dp[pos][lima][limb][g+1][l+1]!=-1) return dp[pos][lima][limb][g+1][l+1];
int lim=((c>>pos)&1);int la=lima?((a>>pos)&1):1;int lb=limb?((b>>pos)&1):1;
ll ret=0;
for(int i=0;i<=la;i++){
for(int j=0;j<=lb;j++){
int tg=g,tl=l;
if(!g && (i&j)<lim && !l && (i^j)>lim) continue;
if(!g && (i&j)<lim) tg=-1;
if(!l && (i^j)>lim) tl=-1;
aa[pos]=i;
bb[pos]=j;
ret+=dfs(pos-1,lima&&(i==la),limb&&(j==lb),tg==-1?-1:((tg==1)||((i&j)>lim)),tl==-1?-1:((tl==1)||((i^j)<lim)));
}
}
dp[pos][lima][limb][g+1][l+1]=ret;
return ret;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(dp,-1,sizeof(dp));
scanf("%lld%lld%lld",&a,&b,&c);
ll ans=dfs(29,1,1,0,0);
ll mi=0;
mi=min(c-1,a)+min(c-1,b)+1;
printf("%lld\n",ans-mi);
}
return 0;
}

A+B problem

64bit IO Format: %lld

题目描述

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. And all the leading zeros are omitted.
For example: the reversed number of 1234 is 4321. The reversed number of 1000 is 1.

We define reversed number of

as

. Given you two positive integers

and

, you need to calculate the reversed sum:

.

输入描述:

The first line of the input gives the number of test cases, T (T≤300)T\ (T \leq 300)T (T≤300).  test cases follow.

For each test case, the only line contains two positive integers: and . (1≤A,B≤231−11 \leq A, B \leq 2^{31}-11≤A,B≤231−1)

输出描述:

For each test case, output a single line indicates the reversed sum.

3
12 1
101 9
991 1

22
11
2

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+10;
string a,b;
ll f(string x){
ll res=0;
int len=x.length();
int ed=len-1;
dep(i,len-1,0) if(x[i]!='0'){
ed=i;break;
}
rep(i,0,ed) res=res*10+x[i]-'0';
return res;
}
void solve(){
cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
ll x=f(a),y=f(b);
ll ans=x+y;
string t=to_string(ans);
reverse(t.begin(),t.end());
int st=0,len=t.length();
rep(i,0,len-1) if(t[i]!='0'){st=i;break;}
rep(i,st,len-1) cout<<t[i];
puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}

0 评论