比賽鏈接

文章目錄

• 求導
• • 題目描述
  • 題解：
• 猜數
• • 題意：
  • 題解：
  • • 方法一 貪心
    • 方法二 暴力
• 答題卡
• • 題意：
  • 題解：
  • 代碼：

求導

鏈接：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

輸入描述:
給出一個數 n
輸出描述:
輸出求 xⁿ求 n - 1 次導后 x 前的系數。(答案對 10⁹+7 取余)
示例1
輸入
復制

5

輸出
復制

120

備注:
對于50% 的數據滿足n≤15

對于%100% 的數據滿足 n≤10 ⁵

題解：

第一次求導，系數為n
第二次求導，系數為n*（n-1）
。。。
第n-1次求導，系數為n*（n-1）…*2
不就是階乘嗎？
直接暴力走起

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn = 1e5 +5;int main(){ll n;cin>>n;ll base=1;for(int i=1;i<=n;i++){base=base*i%mod;}cout<<base<<endl;return 0; }

猜數

鏈接

題意：

n個數改動前之和是大于等于m，現在給出改動后，問最少改動幾個數字？

輸入

2 3 1 1

輸出

1

題解：

方法一 貪心

我們從最小的數字開始改，同時記錄每個數字的次數
有兩種情況要記錄個數：第一個是把還未修改的最小數改成最大數（9）后總值還是沒m大，那這個數一定要改
另一個是改完當前數就正好滿足條件，那也記入答案，結束
因為數的范圍都在0到9，所以可以用桶來存每個數，這樣操作時同時多個操作

#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 4; int n,m,a[maxn]; int tong[12]; int main() {cin>>n>>m; int sum = 0,num,ans,tot=0;for(int i=1;i<=n;i++){cin>>a[i];tong[9 - a[i]]++;sum += a[i];}for(int i=9;i>=0;i--){if(sum >= m) break;ans = tong[i] * i;if(sum + ans < m) {sum += ans;tot += tong[i];}else{num = ((double)(m - sum)/(double)i+0.9);tot += num;sum += num * i;}}cout << tot << endl;return 0; }

方法二 暴力

貌似直接暴力就可以過
排個序，然后從小將每個數補滿（補到9），如果補后大于m，輸出當前數的序號，如果沒補滿繼續

答題卡

題意：

題解：

dp做法
我們要先知道所選格子的橫列不能沖突，因為每個題只能有一個答案。。。

如果我們選中第一行第一列的格子，反轉后還是本身，因為行列不能再選，所以剩下就成了(n-1) * (n-1)的問題
如果選的是第一行第二列，對稱位置是第二行第一列，也就是第一二行和第一二列都不能再選了，就成了(n-2) * (n-2)的問題
第三行到第n行與第二種情況一樣，都變成了(n-2) * (n-2)的問題
匯總一起：
第一種情況為dp[i-1]，出現一次
第二種情況為dp[i-2]，出現了n-1次
dp[n]=dp[n-1]+(n-1)*dp[n-2]

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+3; ll dp[maxn]; int main(){dp[0] = 1;dp[1] = 1;dp[2] = 2;dp[3] = 4;ll n;cin>>n;for(int i = 4 ; i <= n ;++i)dp[i] = (dp[i-1] + (i-1)*dp[i-2])%mod;cout<<dp[n]<<endl; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客IOI周赛16-普及组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。