"Weilai Cup" 2022 Niuke summer multi school training camp 1

G greedy

Lexicographical Maximum

The question ：

Given n, seek 1~n The string with the largest lexicographic order in

Ideas ：

Obvious , The answer removes the last one , The rest are 9 ;

if n Remove the last one , The rest are 9 The answer is n

If not, the answer is |n| − 1 individual 9, among |n| finger n The length of the corresponding string

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;

using namespace std;
string s;
void solve()
{
    cin>>s;
    int len=s.length();
    bool flag=1;
    for(int i=0;i<len-1;i++)
    {
        if(s[i]!='9')
        {
            flag=0;
            break;
        }
    }
    if(flag) cout<<s<<'\n';
    else 
    {
        for(int i=0;i<len-1;i++) cout<<'9';
        cout<<'\n';
    }
}
int main()
{
    //ios;
    int _t=1;
    //cin>>_t;
    while(_t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

A Interval merging

Villages: Landlines

The question ：

  Ideas ：

Equivalent power stations and buildings to sections [ x-r , x+r ];

Then interval merging

Because power towers can be built indefinitely , Therefore, power towers can be built in the section , Then the merged interval must be connected  

The answer is the length of the number axis that is not covered by the interval

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=2e5+10;
const int inf=0x3f3f3f3f;

using namespace std;
int n;
struct node{
    int l,r;
}p[N];
int cnt;
bool cmp(node a,node b)
{
    return a.l<b.l;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        p[++cnt].l=a-b;p[cnt].r=a+b;
    }
    sort(p+1,p+n+1,cmp);
    //for(int i=1;i<=n;i++) cout<<p[i].l<<' '<<p[i].r<<'\n';
    int x=p[1].l,y=p[1].r;
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        if(p[i].l>y) 
        {
            ans+=p[i].l-y;
            x=p[i].l,y=p[i].r;
        }
        else
        {
            x=min(x,p[i].l);
            y=max(y,p[i].r);
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    //ios;
    int _t=1;
    //cin>>_t;
    while(_t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

D Computational geometry

Mocha and Railgun

The question ：

Given a circle and a point strictly located in the garden Q

It can be downloaded from Q Point to any angle to emit a width of 2d Electromagnetic cannon

The midpoint of the electromagnetic gun is Q, And both ends are located in the circle during the rotation

Ask the maximum arc length that can be destroyed by a single shot

 

Ideas ： Find the longest arc and convert it into the corresponding string FG The longest , Again because FG by ▲FGH Beveled edge of ,FH be equal to 2d, So when GH The longest time , The longest arc ;

It can be derived that when the emission direction is perpendicular to OQ when , The longest arc

 

 ​​​​​​​​​​​​​​

  from OE,OB Angle of length β, from OA,OD Dejiao α, The answer is （β-α）* R

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define PII pair<int,int>
typedef long long ll;
const double PI=acos(-1.0);
const int N=1e6+10;
const int inf=0x3f3f3f3f;

using namespace std;
int r,x,y,d;
void solve()
{
    cin>>r;
    cin>>x>>y>>d;
    double p=sqrt(1.0*x*x+1.0*y*y);
    double a=acos((1.0*p+d)/r);
    double b=acos((1.0*p-d)/r);
    //cout<<a<<' '<<b;
    double ang=b-a;
    printf("%.8f\n",(double)ang*r);
}
int main()
{
    //ios;
    int _t=1;
    cin>>_t;
    while(_t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

 I probability DP

Chiitoitsu

The question ：

  Ideas ： The best strategy is to touch a card and form a pair with the single card in your hand , Throw away a single card , If it doesn't form a pair , Then throw away the card you touched .

 

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=136-13;
const int inf=0x3f3f3f3f;
const int p=1e9+7;
using namespace std;
int mp[125];
string s;
int hand[10][125];
int f[150][15];
int qmi(int x,int k,int p)
{
    int ret=1;
    while(k)
    {
        if(k&1) ret=(ll)ret*x%p;
        k>>=1;
        x=(ll)x*x%p;
    }
    return ret;
}
void pre()
{
    mp['m']=0;mp['p']=1;mp['s']=2;mp['z']=3;
    for(int i=0;i<=N;i++)
    {
        int inv=qmi(i,p-2,p);
        for(int j=0;j<=13;j++)
        {
            if(j==0) f[i][j]=0;
            else
            {
                f[i][j]=(1ll*(i-3*j)*(f[i-1][j]+1)%p*inv+1ll*3*j*(f[i-1][j-2]+1)%p*inv)%p;
            }
        }
    }
}

void solve(int cnt)
{
    memset(hand,0,sizeof hand);
    cin>>s;
    int len=s.length();
    for(int i=0;i<len;i+=2)
    {
        hand[s[i]-'0'][mp[s[i+1]]]++;
    }
    int single=0;
    for(int i=1;i<=9;i++)
    {
        for(int j=0;j<=3;j++)
        {
            if(hand[i][j]==1) single++;
        }
    }
    printf("Case #%d: %d\n",cnt,f[N][single]);
}
int main()
{
    //ios;
    int _t=1;
    cin>>_t;
    pre();
    int t=1;
    while(_t--)
    {
        solve(t++);
    }
    system("pause");
    return 0;
}