2020牛客暑期多校训练营（第五场） D. Drop Voicing E. Bogo Sort F. DPS I. Hard Math Problem
DEFI
题意：
给你一个数列，你可以进行两种操作。
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最大，然后再用数列长度减去。但是至于对不对，我也不太会证明.... 作为一个菜鸡，大胆猜测，直接交一发验证（逃。可以看看这个巨巨的证明，感觉讲的蛮清楚的了。
代码
1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 #define ll long long 4 #define pb push_back 5 #define ft first 6 #define sd second 7 #define pii pair<int,int> 8 #define pll pair<ll,ll> 9 using namespace std; 10 11 int a[100100],b[510]; 12 int dp[510]; 13 const int INF=0x3f3f3f3f; 14 15 int main() 16 { 17 ios::sync_with_stdio(false); 18 cin.tie(0); 19 cout.tie(0); 20 int n; 21 cin>>n; 22 int ans=-1; 23 for(int i=0;i<n;i++) cin>>a[i]; 24 for(int k=0;k<n;k++){ 25 for(int i=0;i<n;i++) dp[i]=INF,b[i]=a[(i+k)%n]; 26 for(int i=0;i<n;i++){ 27 int p=lower_bound(dp,dp+n,b[i])-dp; 28 ans=max(ans,p+1); 29 dp[p]=b[i]; 30 } 31 } 32 cout<<n-ans<<endl; 33 return 0; 34 }
E. Bogo Sort
题意
给定一个置换，问有多少个排列可以通过若干次该置换变成1....N的排列。结果对10^N取模
题解
- 由于环长度总和是n，所以一定不会大于n 位数，不需要取模。
- 写几组观察可以看出结果就是所有环的lcm，然后用大数运算。
代码
贴上队友巨巨的代码
1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 #define ll long long 4 #define pb push_back 5 #define ft first 6 #define sd second 7 #define pii pair<int,int> 8 #define pll pair<ll,ll> 9 using namespace std; 10 11 const int maxn = 1e5+5; 12 int a[maxn]; 13 14 vector<int> cheng(int x,vector<int> vv) 15 { 16 vector<int> ans; 17 int t=0; 18 int i; 19 for (i=0;i<vv.size();i++) 20 { 21 t=t+vv[i]*x; 22 ans.push_back(t%10); 23 t/=10; 24 } 25 while (t>0) 26 { 27 ans.push_back(t%10); 28 t/=10; 29 } 30 31 return ans; 32 } 33 34 int num[maxn]; 35 int vis[maxn]; 36 37 int main() 38 { 39 int n; 40 scanf("%d",&n); 41 for (int i=1 ; i <= n; i ++ ) 42 { 43 scanf("%d",&a[i]); 44 } 45 std::vector<int> ans; 46 ans.pb(1); 47 int gc = 0; 48 int ftemp = 0; 49 for (int i = 1; i <= n; i ++ ) 50 { 51 if(vis[i] == 0) 52 { 53 int s= 0 ; 54 int k= i; 55 while(vis[k] == 0) 56 { 57 vis[k] = 1; 58 // printf("%d ",k); 59 k = a[k]; 60 s ++ ; 61 62 } 63 ftemp ++ ; 64 for (int i = 2; i * i <= s; i ++ ) 65 { 66 int cnt = 0; 67 while(s % i == 0) 68 { 69 s /= i; 70 cnt ++ ; 71 } 72 num[i] = max(num[i],cnt); 73 } 74 if(s > 1) 75 { 76 num[s] = max(num[s],1); 77 } 78 } 79 } 80 for (int i = 2; i <= n; i ++ ) 81 { 82 for (int j = 0; j < num[i]; j ++ ) 83 { 84 ans = cheng(i,ans); 85 } 86 } 87 int f = 1; 88 for (int i = min(n - 1,(int)ans.size()) - 1; i >= 0; i -- ) 89 { 90 if(ans[i] != 0 || f == 0) 91 { 92 f =0 ; 93 printf("%d",ans[i]); 94 } 95 } 96 printf(" "); 97 }
F. DPS
题意
输出一个图形。si=
，si就是图中 ‘-’ 的数量。如果当前 di==maxidi 的话，就要在中间那行的 '|' 前边输出一个 ‘*’ 。
题解
记得开long long ，因为算 si 的时候 d 的最大范围*50的话会超过long long
代码
1 #include<bits/stdc++.h> 2 #define ull unsigned long long 3 #define ll long long 4 #define pb push_back 5 #define ft first 6 #define sd second 7 #define pii pair<int,int> 8 #define pll pair<ll,ll> 9 using namespace std; 10 11 ll a[10010]; 12 13 int main() 14 { 15 ios::sync_with_stdio(false); 16 cin.tie(0); 17 cout.tie(0); 18 ll n; 19 cin>>n; 20 ll maxn=0; 21 for(ll i=0;i<n;i++) cin>>a[i],maxn=max(maxn,a[i]); 22 for(ll i=0;i<n;i++){ 23 ll p=(50*a[i]+maxn-1)/maxn; 24 cout<<"+"; 25 for(ll i=0;i<p;i++) cout<<"-"; 26 cout<<"+"<<endl; 27 28 cout<<"|"; 29 if(a[i]==maxn){ 30 for(ll i=0;i<p-1;i++) cout<<" "; 31 cout<<"*|"; 32 cout<<a[i]<<endl; 33 } 34 else{ 35 36 for(ll i=0;i<p;i++) cout<<" "; 37 cout<<"|"; 38 cout<<a[i]<<endl; 39 } 40 41 cout<<"+"; 42 for(ll i=0;i<p;i++) cout<<"-"; 43 cout<<"+"<<endl; 44 } 45 return 0; 46 }
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不相邻。
可以计算出这是上限。
代码
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 int main(){ 5 printf("0.666667 "); 6 return 0; 7 }