A. Array and Peaks
題目大意：尋找一個n的排列，使得這個排列有k個峰值，
思路：從i=2每隔兩個數放置一個當前沒有放的最大值，在放k個之后就停止（如果不足k個就輸出-1），接著繼續從i=1開始，沒有放置數字的位置接著放置當前沒有放的最大值，
#include <iostream>
#include <unordered_map>
#include <cstring>
using namespace std;
typedef long long ll;
unordered_map<int,ll> mp;
const int N = 110;
int a[N],vis[N];
int main()
{
int t;cin>>t;
while(t--)
{
memset(a,0,sizeof a);
int n,k;cin>>n>>k;
int cnt = n;
int now = 0;
for(int i=2;i<n&&k;i+=2)
a[i] = cnt--,k--;
if(k){
puts("-1");
continue;
}
for(int i=1;i<=n;i++)
if(!a[i]) a[i] = cnt--;
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
puts("");
}
return 0;
}
B. AND Sequences
給定一個陣列a，詢問a有多少種排列方式，使得每一個i,都有a1&a2&…&ai=ai+1&ai+2&…&an
思路：通過&的性質，發現這是一道排列組合題，
當時在做這道題時，注意到幾個數字在一起&，結果只會越來越小， 于是就思考到找來a陣列中的最小值，并且一頭一尾放一個，中間的n-2個數字隨便排 ； 記cnt為最小數字的個數，答案即為(cnt-1)*cnt*(n-2)!
然而很不幸的wa了，但是找最小值這個思路應該不會錯吧，再次思考后發現，我們要尋找的“最小值”應該是a中所有數字&后的結果，這個結果如果在a中存在，那么就是最小值，如果不存在，就無解了，
代碼：
#include <iostream>
#include <unordered_map>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 200010,mod = 1e9+7;
int a[N];
ll p[N];
int main()
{
p[0] = p[1] = 1;
for(int i=2;i<=200000;i++)
p[i] = (p[i-1]*i)%mod;//預處理階乘
int t;cin>>t;
while(t--)
{
ll n;cin>>n;
scanf("%d",&a[1]);
int minn = a[1];
for(int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
minn&=a[i];
}
ll cnt = 0;
for(int i=1;i<=n;i++)
if(a[i]==minn) cnt++;
if(cnt<2)
{
puts("0");
continue;
}
ll res = cnt*(cnt-1)%mod*p[n-2]%mod;
printf("%lld\n",res);
}
return 0;
}
Add One
題目大意：給定一個數字n，進行m次操作，每次可以給n的每一位數字加1，求最后n的位數，
思路：這是一道dp問題，我們可以單獨的考慮n的每一位數字在進行m次操作后的位數，最后累加即可，
又注意到，不同的數字（0~9）在進行m次累加后的結果是有關聯的，因此我們直接定義dp陣列f[i]為數字10進行了i次操作后的位數， f[i] = f[i-9]+f[i-10] 初始化：f[0~8] = 2,f[9] = 3;
有了這個dp陣列之后，我們就可以通過10 來計算出0~9的結果了
代碼：
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
unordered_map<int,ll> mp;
const int N =200010,mod = 1e9+7;
int f[N];
void init()
{
for(int i=0;i<=8;i++) f[i] = 2;
f[9] = 3;
for(int i=10;i<=200000;i++) f[i] = (f[i-9]+f[i-10])%mod;
}
int main()
{
init();//初始化
int t;scanf("%d",&t);
int n,m;
while(t--)
{
int res = 0;
int a[20],cnt = 0;
scanf("%d%d",&n,&m);
while(n) a[++cnt] = n%10,n/=10;
for(int i=1;i<=cnt;i++)
if(a[i]+m<10) res = (res+1)%mod;
else res = (res+f[m-(10-a[i])])%mod;
printf("%d\n",res);
}
return 0;
}
為什么沒有D？因為菜
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/275518.html
標籤：其他