DEFI

D. Drop Voicing

题意：

给你一个数列，你可以进行两种操作。
Drop-2: 将n-1位置的数移到第一个位置，变成 pn−1, p1, p2, …, pn−3, pn−2, pn。
Invert: 将第一个数移动到最后一个位置，变成  p2, …, pn−3, pn−2, pn−1,pn, p1。
每次操作可以选择一种不限次数的移动，问Drop-2操作最少几次。

题解：

比赛的时候看这样例突然就有了想法，感觉就是不在自己该在的地方的数才需要Drop-2变换，也就是说找到先最长升序数列（LIS），然后剩下的数操作一次Drop-2应该就可以变换到他该去的地方，只要用数列长度减去LIS就好了。因为Invert操作并不需要考虑他的次数，所以可以先操作Invert，找到一个排序的LIS最大，然后再用数列长度减去。但是至于对不对，我也不太会证明.... 作为一个菜鸡，大胆猜测，直接交一发验证（逃。可以看看这个巨巨的证明，感觉讲的蛮清楚的了。

代码 

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

int a[100100],b[510];
int dp[510];
const int INF=0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int ans=-1;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++) dp[i]=INF,b[i]=a[(i+k)%n];
        for(int i=0;i<n;i++){
            int p=lower_bound(dp,dp+n,b[i])-dp;
            ans=max(ans,p+1);
            dp[p]=b[i];
        }
    }
    cout<<n-ans<<endl;
    return 0;
}

E. Bogo Sort

题意

给定一个置换，问有多少个排列可以通过若干次该置换变成1....N的排列。结果对10^N取模

题解

  • 由于环长度总和是n，所以一定不会大于n 位数，不需要取模。
  • 写几组观察可以看出结果就是所有环的lcm，然后用大数运算。

代码

贴上队友巨巨的代码 
#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

const int maxn = 1e5+5;
int a[maxn];

vector<int> cheng(int x,vector<int> vv)
{
    vector<int> ans;
    int t=0;
    int i;
    for (i=0;i<vv.size();i++)
    {
        t=t+vv[i]*x;
        ans.push_back(t%10);
        t/=10;
    }
    while (t>0)
    {
        ans.push_back(t%10);
        t/=10;
    }
 
    return ans;
}

int num[maxn];
int vis[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for (int  i=1 ; i <= n; i ++ )
    {
        scanf("%d",&a[i]);
    }
    std::vector<int> ans;
    ans.pb(1);
    int gc = 0;
    int ftemp = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if(vis[i] == 0)
        {
            int s= 0 ;
            int  k= i;
            while(vis[k] == 0)
            {
                vis[k] = 1;
                // printf("%d ",k);
                k = a[k];
                s ++ ;
                 
            }
            ftemp ++ ;
            for (int i = 2; i * i <= s; i ++ )
            {
                int cnt = 0;
                while(s % i == 0)
                {
                    s /= i;
                    cnt ++ ;
                }
                num[i] = max(num[i],cnt);
            }
            if(s > 1)
            {
                num[s] = max(num[s],1);
            }
        }
    }
    for (int i = 2; i <= n; i ++ )
    {
        for (int j = 0; j < num[i]; j ++ )
        {
            ans = cheng(i,ans);
        }
    }
    int f = 1;
    for (int i = min(n - 1,(int)ans.size()) - 1; i >= 0; i -- )
    {
        if(ans[i] != 0 || f == 0)
        {
            f =0 ;
            printf("%d",ans[i]);
        }
    }
    printf("\n");
}


F. DPS

题意

输出一个图形。，si就是图中 ‘-’ 的数量。如果当前 di==maxidi 的话，就要在中间那行的 '|' 前边输出一个 ‘*’ 。

题解

记得开long long ，因为算 si 的时候 d 的最大范围*50的话会超过long long

代码 

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
 
ll a[10010];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll maxn=0;
    for(ll i=0;i<n;i++) cin>>a[i],maxn=max(maxn,a[i]);
    for(ll i=0;i<n;i++){
        ll p=(50*a[i]+maxn-1)/maxn;
        cout<<"+";
        for(ll i=0;i<p;i++) cout<<"-";
        cout<<"+"<<endl;
 
        cout<<"|";
        if(a[i]==maxn){
            for(ll i=0;i<p-1;i++) cout<<" ";
            cout<<"*|";
            cout<<a[i]<<endl;
        }
        else{
 
            for(ll i=0;i<p;i++) cout<<" ";
            cout<<"|";
            cout<<a[i]<<endl;
        }
 
        cout<<"+";
        for(ll i=0;i<p;i++) cout<<"-";
        cout<<"+"<<endl;
    }
    return 0;
}

I. Hard Math Problem

题意

每一个H的周围至少要有一个G和一个E，f (n,m) 代表n*m的格子中H的最大数量是多少。求。

题解

(i+j)%3 =0 交错2和3 

答案是2/3 

因为这样每个1旁边恰好有一个2和3，而任意两个2和3不相邻。

可以计算出这是上限。

代码 

#include <cstdio>
#include <iostream>
using namespace std;
int main(){
    printf("0.666667\n");
    return 0;
}