A 愛麗絲的人偶（一）
思路： 先排小的，然后插空排大的就好了，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=0x3f3f3f3f;
int a[1000007];
int main()
{
int n;
cin>>n;
int e;
if(n%2==0){
e=n/2;
}else{
e=n/2+1;
}
int cnt=1;
for(int i=1;i<=e;i++){
a[cnt]=i;
cnt+=2;
}
cnt=2;
for(int i=e+1;i<=n;i++){
a[cnt]=i;
cnt+=2;
}
for(int i=1;i<=n;i++){
if(i==1)printf("%d",a[i]);
else printf(" %d",a[i]);
}
return 0;
}
B 愛麗絲的人偶（二）
思路： 找出有幾個種人偶（用map），然后在m種人偶中取k個，是組合數，記得觸除法的時候求逆元，組合數m!/((m-k)!*k!);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
map<ll,ll>mp;
ll sum[1000007];
ll qpow(ll x,ll y){
ll ans=1;
while(y>0){
if(y&1)ans=ans*x%mod;
y/=2;
x=x*x%mod;
}
return ans;
}
int main()
{
ll n,k;
cin>>n>>k;
int cnt=0;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
if(mp[x]==0){
mp[x]++;
cnt++;
}else{
mp[x]++;
}
}
sum[0]=1;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]*i%mod;
}
ll ans;
if(cnt>=k)
ans=sum[cnt]*qpow(sum[cnt-k]*sum[k]%mod,mod-2)%mod;
else
ans=0;
printf("%lld\n",ans);
return 0;
}
C 打毛玉大賽
思路： 只有一只血是1一只血是2的時候輸出A，其他都是輸出B，可以自己模擬一下，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=0x3f3f3f3f;
int main()
{
ll a,b;
cin>>a>>b;
if(a==1&&b==1){
printf("B\n");
}else if((a==1&&b==2)||(a==2&&b==1)){
printf("A\n");
}else{
printf("B\n");
}
return 0;
}
D 貪玩的二小姐（續）
思路： 如果是奇數個括號那么肯定不行，輸出-1，如果是偶數就模擬一下，看看剩下幾個‘（’和幾個‘）’，如果是奇數個的就必須有一個要和另一種括號配對，這個括號要變，如果是偶數個就可以內部配對，兩個同類括號只用變一個括號就可以完成配對，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[1000007];
int main(){
int n;
cin>>n;
scanf("%s",a+1);
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++){
if(a[i]=='('){
cnt1++;
}else if(a[i]==')'&&cnt1!=0){
cnt1--;
}else{
cnt2++;
}
}
if(n%2==1)printf("-1\n");
else{
int ans=0;
ans+=cnt1/2;
ans+=cnt2/2;
if(cnt1%2==1)ans++;
if(cnt2%2==1)ans++;
printf("%d\n",ans);
}
return 0;
}
E 游戲機本當下手
思路： 先求出每一段的01有幾個存下來，如果按一次的話就把每種情況都列一下，在每一部分里求和就好了，如果是多次的話只知道兩邊的數各有多少個，然后把兩個數相乘，就是這一段的取法個數，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[1000007];
char a[1000007];
ll zhuan[1000007];
int main(){
int n,k;
cin>>n>>k;
scanf("%s",a+1);
int cnt=1;
zhuan[cnt]=1;
for(int i=2;i<=n;i++){
if(a[i]!=a[i-1]){
cnt++;
}
zhuan[cnt]++;
}
if(k>cnt){
printf("0\n");
}else{
ll ans=0;
if(k==1){
for(int i=1;i<=cnt;i++){
ans+=(zhuan[i]+1)*zhuan[i]/2;
}
}else{
for(int i=1;i<=cnt-k+1;i++){
ans+=zhuan[i]*zhuan[i+k-1];
}
}
printf("%lld\n",ans);
}
return 0;
}
F 宵暗的妖怪
思路： 只要做個小dp，我加進去一個新數，那么我們現在只要比較把i-1變成取的數和不把i-1變成取的數哪個比較大就取哪個就行了，
f[i]=max(f[i-3]+a[i-1],f[i-1]);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100007];
ll a[100007];
int main(){
ll n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i>2){
f[i]=max(f[i-3]+a[i-1],f[i-1]);
}
}
printf("%lld\n",f[n]);
return 0;
}
G 魔界伊始
思路 我們要判斷最小的可能得到的數字是多少，因為程序于輾轉相除法類似，所有就相當于求所有數的最大公倍數，我們先排序一下，然后找出最小的最大公倍數，只要查詢的數的數是最小的最小公倍數的倍數，就一定能成功，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q;
ll a[100007];
int main(){
cin>>n;
int flag=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ll minn=1e18+7;
sort(a+1,a+1+n);
for(int i=2;i<=n;i++){
ll x=__gcd(a[i],a[i-1]);
minn=min(minn,x);
}
cin>>q;
if(minn==1)flag=1;
while(q--){
ll e;
cin>>e;
if(flag==1||e%minn==0)printf("Yes\n");
else printf("No\n");
}
return 0;
}
H 芭芭拉沖鴨~
思路： 因為他保證形成一個樹，所以我們只要bfs，找到每個點從所有子節點過來最長的兩條邊，然后把他們的和就是在這個小子樹下最長的邊，每次只要回傳最長的邊就行（單獨的），對于每一條形成的邊判一下大小就行了，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>s[100007];
int cc[100007];
ll maxx=0;
ll dfs(int root,int fa){
if(s[root].size()==0){
return 0;
}
ll maxn1=0,maxn2=0;
for(int i=0;i<s[root].size();i++){
int v=s[root][i];
if(v==fa)continue;
ll e=dfs(v,root);
if(cc[v]!=cc[root]){
if(e+1>maxn1){
maxn2=maxn1;
maxn1=e+1;
}
else maxn2=max(maxn2,e+1);
}
}
maxx=max(maxx,maxn1+maxn2);
return maxn1;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char x;
cin>>x;
if(x=='R'){
cc[i]=1;
}
if(x=='G'){
cc[i]=2;
}
if(x=='B'){
cc[i]=3;
}
}
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
s[u].push_back(v);
s[v].push_back(u);
}
dfs(1,-1);
printf("%lld\n",maxx);
return 0;
}
I 永遠亭的小游戲
思路： 我們發現，易得每一次的乘積事實上就是a[i]sumbsumc，這時候所有乘積的和就很好算了，然后把和除以三個陣列的大小相乘就行了，注意取模和逆元，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll a[1000007],b[1000007],c[1000007];
ll qpow(ll x,ll y){
ll ans=1;
while(y>0){
if(y&1)ans=ans*x%mod;
y/=2;
x=x*x%mod;
}
return ans;
}
int main(){
ll n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
ll x=0,y=0,z=0;
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(ll i=1;i<=m;i++){
scanf("%lld",&b[i]);
y+=b[i];
y%=mod;
}
for(ll i=1;i<=k;i++){
scanf("%lld",&c[i]);
z+=c[i];
z%=mod;
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=(ans+a[i]*y%mod*z%mod)%mod;
}
printf("%lld\n",ans*qpow(n*m%mod*k%mod,mod-2)%mod);
return 0;
}
K 玩具銷售員
思路： 一次能檢查兩個物品，我們算出一共能檢查多少個物品，然后再比較讓我們查的物品數量就行了，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=0x3f3f3f3f;
int a[1000007];
int main()
{
int n,m,k;
cin>>n>>m>>k;
if(2*k>=m){
printf("Yes\n");
}else{
printf("No\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226313.html
標籤：其他
上一篇：2020年csp總結