文章中可能有不太恰當地方，還請大家指正，
是否因為出題人的簡短題解而發愁?，是否看不懂出題人的變態模板標程?是否因為自己是小白而苦惱？來看這片文章，幫助你解決這些問題
如果有識訓請點個贊再走吧，還有幾道題沒來得及寫上去，之后會慢慢補上的
1001.收集金幣
題目鏈接
演算法：動態規劃
狀態dp思路：
f[i][0]表示前i個操作中一直沒有跳的最大金幣數量
f[i][1]表示前i個操作中已經跳過或者現在跳的最大金幣數量
狀態轉移：
f[i][0]很簡單只有一種狀態
f[i][0]=f[i-1][0]+x
f[i][1]有兩種狀態可以轉移過來
1.f[i][1]可以是第i個操作跳過即前i-1沒有跳過即f[i-1][0]
2.前i-1已經跳過了，現在不需要跳過f[i-1][1]-x
所以
f[i][1]=max(f[i-1][0],max(f[i-1][1]-x,0ll))
最終狀態
f[n][0]從頭到尾一次都沒跳過
f[n][1]只跳過一次的最大值
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
typedef long long LL;
LL f[N][2];
int main()
{
int T,n,x;
string s;
cin>>T;
while(T--)
{
memset(f,0,sizeof f);
f[0][0]=0;
f[0][1]=-1e5;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s>>x;
if(s=="LOST")
{
f[i][1]=max(f[i-1][0],max(0ll,f[i-1][1]-x));
f[i][0]=max(0ll,f[i-1][0]-x);
}
else
{
f[i][0]=f[i-1][0]+x;
f[i][1]=f[i-1][1]+x;
}
}
cout<<max(f[n][0],f[n][1])<<endl;
}
}
1002.使用技能
題目鏈接
演算法：乘法逆元+快速冪
題意：這道題題目意思比較難懂，代碼比較簡單，由題意知序列的總數量是m^n的，我們需要先計算出所有序列的價值和，再除以序列總數量，
因為序列存在排序狀態，因此每個序列都不一樣，我們直接列舉釋放x次技能的總數量，再加起來較為簡便，首先需要從n個序列中挑選出x個位置即C（n，x）然后乘以m個技能，因為每個技能都可以，在把其他位置填滿即可即（m-1）^(n-x)最后乘以每個價值x^2
公式為C（n,x）*m*(m-1)^(n-x)*x^2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
const int mod = 1e9+7;
const int maxn = 100000;
LL n,m;
LL jc[N],ni[N];
LL qmi(LL a,LL b)
{
LL ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
LL C(LL n,LL m)
{
return jc[n]*ni[m]%mod*ni[n-m]%mod;
}
int main()
{
int T;
cin>>T;
jc[0]=1;
for(int i=1;i<=maxn;i++)jc[i]=jc[i-1]*i%mod;
ni[maxn]=qmi(jc[maxn],mod-2);
for(int i=maxn-1;i>=0;i--)ni[i]=ni[i+1]*(i+1)%mod;
while(T--)
{
cin>>n>>m;
LL res=0;
for(int i=1;i<=n;i++)
{
res=res+C(n,i)*i%mod*i%mod*m%mod*qmi(m-1,n-i)%mod;
res%=mod;
}
res=res*qmi(qmi(m,n),mod-2)%mod;
cout<<res<<endl;
}
}
1003.歡度佳節
題目鏈接
演算法：位運算+暴搜
思路：題目求占領的最大方塊，所以篩子數值就假設每次一定是6，仔細看題，糖果庫存大于某個格子的數值，且這個格子與你占領的格子相鄰，那么你可以選擇占領這個格子這里的大于容易理所應當的看成大于等于，所以每個格子需要的擲投數量就是a[i]=a[i]/6+1
本題需要先把輸入的一維資料轉化為二維，用方位陣列dx【】，dy【】進行每個方位判斷，之后根據位運算，再把二維轉化為一維，
因為是17個格子，所以2^17不會超時，可以暴力來做，用二進制列舉每一個狀態，是1則表示會到這個格子上，0則反之，每個二進制數字再進行判斷是否符合題目要求，如果符合找出二進制中1的個數，每次更新，求最大值即可，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 17;
int x[]={1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5};
int y[]={1,2,4,5,2,3,4,2,3,4,2,3,4,1,2,4,5};
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int a[20],mp[20][20];
bool st[20];
int n;
int arrive=0,sum=0;
void dfs(int x,int y,int state)
{
//這里的arrive用于判斷路徑的連通性和進行判重，不再走原來走過的路
int id=mp[x][y];
if((id==-1)||(state>>id)%2==0||(arrive>>id)%2==1)return ;
sum+=a[id];
arrive|=1<<id;
for(int i=0;i<4;i++)
{
dfs(x+dx[i],y+dy[i],state);
}
}
int main()
{
memset(mp,-1,sizeof mp);
//二維轉化為一維為了進行位運算判斷
for(int i=0,cnt=0;i<N;i++)
mp[x[i]][y[i]]=cnt++;
int T;
cin>>T;
while(T--)
{
for(int i=0;i<N;i++)
{
cin>>a[i];
a[i]=a[i]/6+1;
}
cin>>n;
int res=0;
//列舉每種狀態
for(int state=0;state<1<<N;state++)
{
//第13個數字是出發點，如果狀態中沒有則直接continue
if((state>>13)%2==0)continue;
arrive=0,sum=0;
//這里的arrive用于判斷路徑的連通性和進行判重，不再走原來走過的路
dfs(x[13],y[13],state);
if(arrive==state&&sum<=n)
{
res=max(res,__builtin_popcount(state));
}
}
cout<<res<<endl;
}
}
1004. 五個小時卷積神經網路從入門到入土
題目鏈接
題太長了，，，，直接把代碼搬過來了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int N = 1e3+7;
template <typename T, typename H>
inline T qpow(const T &a, const H &p, const int &mo = MOD) {
long long res = 1, x = a;
for (H i = p; i; i >>= 1, x = x*x%mo)
if (i&1) res = res*x%mo;
return static_cast<T>(res);
}
int n, m;
char s[N];
const ll inv = qpow(4, MOD-2);
signed main() {
int T = 1;
scanf("%d", &T);
while (T--){
scanf("%d%d", &n, &m);
ll ans = 0, sumw = 0;
for (int i = 0; i < 3; ++i)
for (int j = 0, w; j < 3; ++j) {
scanf("%d", &w);
sumw += w;
}
for (int i = 0; i < n; ++i) {
scanf("%s", s);
for (int j = 0; j < n; ++j)
ans += s[j] == '1';
}
ans = ans*qpow(sumw*inv%MOD, m)%MOD;
printf("%lld\n", ans);
}
return 0;
}
1005.闖關游戲
題目鏈接
演算法：01背包+貪心
思路：這道題比較巧妙，看起來像分組背包，但其實不是，先根據貪心的思路進行判斷，把一個空間更小的數放進背包，在把差值跑一邊01背包，非常巧妙
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=6010;
int a[N],b[N],c[N],d[N];
int f[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
memset(f,0,sizeof f);
int res=0,now=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i]>>d[i];
for(int i=1;i<=n;i++)
{
if(a[i]>c[i])
{
swap(a[i],c[i]);
swap(b[i],d[i]);
}
if(b[i]>d[i])
{
d[i]=b[i];
}
if(m<a[i])break;
m-=a[i];
now+=b[i];
c[i]-=a[i];
d[i]-=b[i];
for(int j=m;j>=c[i];j--)
{
f[j]=max(f[j],f[j-c[i]]+d[i]);
}
res=max(res,now+f[m]);
}
cout<<res<<endl;
}
}
1006.軍訓
題目鏈接
演算法：打表+玄學盲猜+數學+注意卡常
本題解摘自：sky123
原文鏈接：https://sky123.blog.csdn.net/article/details/121102090
通過小范圍打表可知，f(n) 增長的非常緩慢，因此可以猜出當 n ≤ 109
時f(n) 不會很大（實際上不會超過17），
設最優解第一個矩陣長寬分別為 x和 x + a ；第二個矩陣長寬分別為y 和 y + b ，則有如下方程：
x ( x + a ) + y ( y + b ) = n
其中 a + b = f ( n ) ，
由于f(n)不會很大,因此首先列舉f(n)，然后列舉 a進而得到 b，之后列舉 x，由于 x在方程中的次數為2，因此列舉范圍為O(
n
\sqrt{n}
n
?) ，
在 a,b,x的值確定之后，原方程可以轉化為關于y的一個二次方程，利用求根公式 O(1)判斷該方程是否有合法的整數解即可確定有無對應方案，
因為列舉 f ( n ) ,a 最壞為90次，因此最終復雜度為O(90T
n
\sqrt{n}
n
?) ，
比較卡常，需要特判幾個f(n) 比較大的 n ，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n;
inline bool check(int d) {
for (int a = 0; a <= d / 2; a++)
for (int x = 1, b = d - a; 1ll * x * x + a * x < n; x++) {
ll s = b * b + 4ll * (n - x * x - a * x), qs = int(sqrt(s));
if (qs * qs == s && (qs - b) % 2 == 0 && qs - b > 0) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> n;
if (n == 551189743 || n == 656865901 || n == 845198527) {
cout << 16 << "\n";
continue;
}
if (n == 608733239) {
cout << 17 << "\n";
continue;
}
int ans;
for (ans = 0;; ans++)
if (check(ans))break;
cout << ans << "\n";
}
return 0;
}
1007.數"X"
題目鏈接
這題寫不出來，，，，，可以參照_sky123_大佬題解
本題解摘自：sky123
原文鏈接：https://blog.csdn.net/qq_45323960/article/details/121102930
單獨考慮 “X” 兩個方向，對于每個方向，將該方向上的元素組成一個序列，記錄每個元素下一次出現的位置，然后二分列舉范圍，使得該范圍中每個元素下一次都只能出現在范圍外，像這樣列舉中心點累加即可得到答案，時間復雜度為 O ( n^2 log ? n ) ，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
struct ST {
int dp[N][10];
void init(const int a[], int n) {
for (int i = 1; i <= n; i++) dp[i][0] = a[i - 1];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int ask(int l, int r) {
int k = __lg(r - l + 1);
return min(dp[l + 1][k], dp[r - (1 << k) + 2][k]);
}
} S;
int a[N][N], n, T;
vector<int> tmp;
vector<pair<int, int>> pos;
int nx[N], cp[1000005];
int c[N][N];
inline void solve() {
int m = (int) tmp.size();
for (int x: tmp)cp[x] = m;
for (int j = m - 1; j >= 0; j--)
nx[j] = cp[tmp[j]], cp[tmp[j]] = j;
S.init(nx, m);
for (int i = 0; i < m; i++) {
int l = 1, r = min(i + 1, m - i);
while (l < r) {
int mid = (l + r + 1) >> 1;
S.ask(i - mid + 1, i + mid - 1) <= i + mid - 1 ? (r = mid - 1) : (l = mid);
}
c[pos[i].first][pos[i].second] = min(l, c[pos[i].first][pos[i].second]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j], c[i][j] = n;
for (int i = 1; i <= n; i++) {
pos.clear(), tmp.clear();
for (int x = 1, y = i; y <= n; x++, y++)
pos.emplace_back(x, y), tmp.push_back(a[x][y]);
solve();
}
for (int i = 1; i <= n; i++) {
pos.clear(), tmp.clear();
for (int x = i, y = 1; x <= n; x++, y++)
pos.emplace_back(x, y), tmp.push_back(a[x][y]);
solve();
}
for (int i = 1; i <= n; i++) {
pos.clear(), tmp.clear();
for (int x = 1, y = i; y >= 1; x++, y--)
pos.emplace_back(x, y), tmp.push_back(a[x][y]);
solve();
}
for (int i = 1; i <= n; i++) {
pos.clear(), tmp.clear();
for (int x = i, y = n; x <= n; x++, y--)
pos.emplace_back(x, y), tmp.push_back(a[x][y]);
solve();
}
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans += c[i][j];
cout << ans << "\n";
}
return 0;
}
1008.小y愛數數
題目鏈接
演算法：快速冪+dp+逆元
這是一個復雜度較高地做法，復雜度為10nlog(n)
思想：最簡單思想是兩層回圈列舉算出余數為k的方法數，再除以n^2就是概率，但本題時間為300ms必然超時，我們可以采取類似埃式篩法篩質數的思想把每個余數為k的數給篩出來
用一個二維陣列存盤f[i][j] i即余數，j即符合要求的數，把f[i][j]預處理出來，用的時候直接使用就可以了，詳細請看代碼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 23333;
const int N = 100010;
int f[12][N];
LL qmi(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
//預處理
for(int i=0;i<=10;i++)
{
//這里的j指的是x，k指的是y，類似于埃式篩法把x的y倍+i的數全部篩出來
//這里x要大于i，如果x小于i，x%y的余數必然不是i
for(int j=i+1;j<=1e5;j++)
{
for(int k=1;k*j+i<=1e5;k++)
{
f[i][k*j+i]++;
}
}
//計算每個余數的方案和
for(int j=1;j<=1e5;j++)f[i][j]+=f[i][j-1];
}
int T;
cin>>T;
LL res=0;
while(T--)
{
int n,k;
cin>>n>>k;
int ans=f[k][n];
//因為預處理時從x大于k的開始了所以這里需要加上那些x等于k的所以加上n-k個
//k等于0時不需要加，因為沒有x和y都不等于0
if(k!=0)ans+=max(n-k,0);
LL state=1ll*ans*qmi((1ll*n*n)%mod,mod-2)%mod;
state=(state+mod)%mod;
res=res^state;
}
cout<<res<<endl;
}
1009.神奇的魔法
題目鏈接
演算法：小根堆的維護+狀態列舉
題意：本題看著好像是背包問題，但是和背包毫無關聯，題意為有多個背包，每個背包有限制，最少拿的數量l[N]和最多拿的數量r[N]，因此題目中一共有所有r[i]-l[i]之和+1種狀態（全部剛好滿足最低l[i]的一種狀態），每種狀態求最大值，在異或起來就是答案.
演算法：如何求每種狀態的最大值呢，用一個動態的最小堆維護就好了，
主要思路：考慮選取物品集合確定的時候一定優先選擇價值大的物品，所以我們可以考慮拿一個堆維護當前選擇價值翻倍的物品，如果是堆中物品 則直接把物品插入堆，否則若物品價值小于堆中最小值則替換，
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 510;
priority_queue<int,vector<int>,greater<int>>heap;
int n,m,k,idx=0;
LL state=0,res=0;
int a[N][N],l[N],r[N];
vector<int>q;
//維護一個動態小根堆
void check(int x)
{
if(heap.size()<k)
{
heap.push(x);
state+=2*x;
}
else if(heap.top()<x)
{
state-=heap.top();
state+=2*x;
heap.pop();
heap.push(x);
}
else state+=x;
}
int main()
{
int T;
cin>>T;
while(T--)
{
//每組資料記得清空
while(heap.size())heap.pop();
idx=0,state=0,res=0;
q.clear();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
sort(a[i]+1,a[i]+m+1,greater<int>());
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&l[i],&r[i]);
//idx統計狀態的數量
idx+=r[i]-l[i];
for(int j=1;j<=l[i];j++)check(a[i][j]);
//把這idx個狀態用vector存盤起來
for(int j=l[i]+1;j<=r[i];j++)q.push_back(a[i][j]);
}
//從大到小排序
sort(q.begin(),q.end(),greater<int>());
res=state;
for(int i=0;i<idx;i++)
{
check(q[i]);
//每種狀態異或起來
res^=state;
}
cout<<res<<endl;
}
}
1010.小凱的書架
因為是概率問題每次列舉到一個位置就去前邊找大于它的第k個數
題目鏈接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=300010;
int a[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
if(i<k)
{
printf("-1\n");
continue;
}
int cnt=0;
for(int j=i-1;j>=0;j--)
{
if(a[j]>a[i])cnt++;
if(cnt==k)
{
printf("%d\n",a[j]);
break;
}
}
if(cnt<k)cout<<-1<<endl;
}
}
}
1011.未成年人之友
純簽到題
題目鏈接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
typedef long long LL;
int main()
{
int T;
cin>>T;
while(T--)
{
string s;
int n,h,m;
cin>>n>>s;
scanf("%d:%d",&h,&m);
if(n>=18)
{
cout<<"Yes"<<endl;
continue;
}
if(s=="Fri"||s=="Sat"||s=="Sun")
{
if(h==20&&m>=0&&m<=59)
{
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
else cout<<"No"<<endl;
}
}
1012.黑曜石
只有水和巖漿相鄰，或者水和巖漿中間只隔了空氣，才可能生成新的黑曜石，因此答案為 一開始的黑曜石數 + 按高度排序后水和巖漿相鄰的個數即為答案，
題目鏈接
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
struct Node
{
int h,type;
bool operator < (const Node & H) const
{
return h<H.h;
}
}a[N];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int res=0;
for(int i=0;i<n;i++)
{
cin>>a[i].type>>a[i].h;
}
sort(a,a+n);
for(int i=0;i+1<n;i++)
{
if((a[i].type==1&&a[i+1].type==2)||(a[i].type==2&&a[i+1].type==1))
{
res++;
}
if(a[i].type==3)res++;
}
if(a[n-1].type==3)res++;
cout<<res<<endl;
}
}
如果有識訓請點個贊再走吧，還有幾道題沒來得及寫上去，之后會慢慢補上的，，，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/347179.html
標籤：其他
上一篇：華為網路配置（RIP）
下一篇：Java——類和物件超詳細總結