2021年廣東工業(yè)大學(xué)第十五屆文遠(yuǎn)知行杯程序設(shè)計(jì)競(jìng)賽（同步賽） 部分題解
?
先聲明，這場(chǎng)我爆0了一題都沒做出來。
?
B題
鏈接：https://ac.nowcoder.com/acm/contest/13504/B
來源：?？途W(wǎng)
?
題目描述
母牛哥在電腦面前坐久了，想站起來看看窗外的小山坡，于是就想出了這個(gè)問題：
給定一個(gè)大小為n的數(shù)組a，序號(hào)從1開始，
計(jì)算:
max{ R - L | 1 <= L <= R <= n, a[L] == a[R], 對(duì)于所有i (L <= i <= R), 滿足a[i] >= a[L] }.
也就是找到兩個(gè)坐標(biāo),這兩個(gè)坐標(biāo)的值相等,并且他們之間的值都大于等于這兩個(gè)坐標(biāo)上的值.
這兩個(gè)坐標(biāo)相減最大能是多少.
?
輸入描述:
第一行一個(gè)整數(shù)n，第二行n個(gè)整數(shù)
輸出描述:
?
輸出題目所求的值
示例1
輸入
5 1 2 3 2 1
輸出
4
說明
當(dāng)L=1，R=5時(shí)，滿足題目條件的最優(yōu)解，答案為R-L=5-1=4
備注:
?
數(shù)據(jù)范圍：
1<=n<=1e6
0<=a[i]<=1e9
?
題解：
棧。
建一個(gè)棧，當(dāng)出現(xiàn)比棧頂小的數(shù)時(shí)，一路往回退，退到小于或等于它的數(shù)。
因?yàn)榇笥谒臄?shù)，絕對(duì)不會(huì)在后面找相同的數(shù)組成區(qū)間，已經(jīng)不滿足條件了，所以可以直接去掉。
往回找，找到小于或等于它的數(shù)。
如果小于它，則表示它仍可以被納入一個(gè)區(qū)間里。
如果等于它，則代表已經(jīng)可以組成一個(gè)兩邊相等中間全比它大的區(qū)間了，就計(jì)算。
但是要注意像 1 2 2 2 1 3 3 1 這樣的數(shù)據(jù)，當(dāng)你第二個(gè)1往回找到第一個(gè)1的時(shí)候，不要將第二個(gè)1入棧，因?yàn)榈谌齻€(gè)1可以和第一個(gè)1組成一個(gè)更長的區(qū)間，這一點(diǎn)需要注意。
?
代碼：
#include<iostream>
#include<stack>
using namespace std;
int n,a[1000006],ans;
stack<int> s;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
s.push(1);
for(int i=2;i<=n;i++)
{
while(!s.empty() && a[s.top()]>a[i])
s.pop();
bool f=false;
if(!s.empty() && a[s.top()]==a[i])
{
ans=max(ans,i-s.top());
f=true;
}
if(!f)
s.push(i);
}
cout<<ans;
return 0;
}?
?
C題
鏈接：https://ac.nowcoder.com/acm/contest/13504/C
來源：牛客網(wǎng)
?
題目描述
母牛哥有一桶油漆,把它用完可以給n平方米的墻涂上顏色.
母牛哥想要在墻上涂5個(gè)正方形(這些正方形的邊長都是整數(shù),單位是米),并且剛好把油漆用完.
母牛哥能做到嗎?
?
輸入描述:
?
第一行一個(gè)數(shù)字t(<=1000),表示測(cè)試樣例數(shù)量
接下來t行,每行一個(gè)數(shù)字n(0<=n<=1000000),表示母牛哥的油漆可以涂多少平方米.
輸出描述:
?
輸出t行,對(duì)于每個(gè)輸入.
如果母牛哥能夠做到,就輸出YES.
否則輸出NO.
示例1
輸入
2 4 55
輸出
NO YES
說明
4顯然不能分解成5個(gè)正平方數(shù),所以這桶油漆不能涂5個(gè)正方形.
55可以涂5個(gè)正方形,他們面積分別是1 4 9 16 25.
?
?
題解：
其實(shí)，只是為了做題的話，先打個(gè)表，暴力算算那些不合適，然后直接特判即可。
具體證明為什么除那些數(shù)外都可以由5個(gè)平方數(shù)組成大家有興趣可以上網(wǎng)查閱資料。
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int a;
cin>>a;
if(a<5 || a==6 || a==7 || a==9 || a==10 || a==12 || a==15 || a==18 || a==33)
cout<<"NO\n";
else
cout<<"YES\n";
}
return 0;
}?
?
E題
鏈接：https://ac.nowcoder.com/acm/contest/13504/E
來源：?？途W(wǎng)
?
題目描述
小明來到一片海灘上，他很喜歡撿貝殼，但他只喜歡質(zhì)量為x的倍數(shù)的貝殼。
貝殼被排列成一條直線，下標(biāo)從1到n編號(hào),小明打算從編號(hào)為區(qū)間[l,r]\left [l,r \right ][l,r]的貝殼中,撿起所有他喜歡的貝殼。你能幫他計(jì)算出他能撿多少貝殼嗎。
給出一個(gè)大小為n(n≤105)n(n\le10^5)n(n≤105)的數(shù)組，下標(biāo)從1到n編號(hào)，a1,a2,...ana_1,a_2,...a_na1?,a2?,...an?(ai≤105)(a_i \le 10^5)(ai?≤105))表示貝殼的質(zhì)量。
給出q(q≤5?104)q(q\le5*10^4)q(q≤5?104)次詢問，每次詢問包含3個(gè)整數(shù)l,r,x(1≤l≤r≤n,1≤x≤105)l,r,x(1\le l \le r\le n,1\le x\le 10^5)l,r,x(1≤l≤r≤n,1≤x≤105)，對(duì)于每次詢問，輸出一行整數(shù),表示這次詢問中能撿到的貝殼數(shù)。
?
輸入描述:
第一行給出兩個(gè)整數(shù)n和q，含義如上所示。
第二行給出n個(gè)整數(shù)表示a1,a2,...ana_1,a_2,...a_na1?,a2?,...an?
接下來q行，每行3個(gè)整數(shù)l,r,x，含義如上所示
輸出描述:
對(duì)于每次詢問輸出該次詢問中能撿到的貝殼數(shù)
示例1
輸入
5 3 1 2 3 4 5 1 3 2 1 5 3 2 5 4
輸出
1 1 1
示例2
輸入
10 3 5532 24380 19363 11022 23965 22383 27049 22357 30453 7451 1 6 2 3 10 10 1 10 9
輸出
3 0 1
?
題解：
實(shí)話講，我不太會(huì)算這題的時(shí)間復(fù)雜度。
這一題，用vector去保留同一個(gè)質(zhì)量的貝殼在的編號(hào)，然后暴力去找就行了。
也挺暴力的。
可以考慮用二分優(yōu)化一下。
?
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int n,q,Max;
int a[100005];
vector<int> v[100005];
void read_in()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
v[a[i]].push_back(i);
Max=max(Max,a[i]);
}
}
int main()
{
read_in();
while(q--)
{
int l,r,x,ans=0;
cin>>l>>r>>x;
for(int k=x;k<=Max;k+=x)
for(int i=0;i<v[k].size();i++)
if(v[k][i]>=l && v[k][i]<=r)
ans++;
cout<<ans<<endl;
}
return 0;
}?
I題
?
鏈接：https://ac.nowcoder.com/acm/contest/13504/I
來源：?？途W(wǎng)
?
題目描述
眾所周知，一個(gè)序列擁有許多非空子序列。
所謂子序列就是在原序列中任意刪除 0 個(gè)或多個(gè)元素，然后保持剩下元素的順序不變所形成的序列。非空子序列集意味著剩下的子序列不能為空。
比如對(duì)于序列[1, 2, 3]，它的所有非空子序列為：[1, 2, 3]，[1, 2]，[1, 3]，[2, 3]，[1]，[2]，[3]。再比如序列 [1, 1]，它的非空子序列有：[1, 1]，[1] (刪除了第一個(gè) 1)，[1] (刪除了第二個(gè)1) 。
現(xiàn)在母牛哥手里有一個(gè)長度為 n 的正整數(shù)序列，他現(xiàn)在要為這個(gè)序列的所有非空子序列打分。對(duì)于一個(gè)序列而言，它的評(píng)分標(biāo)準(zhǔn)為序列里所有數(shù)的乘積（只有一個(gè)數(shù)的序列，分?jǐn)?shù)就是這個(gè)數(shù)）。
母牛哥想要知道所有分?jǐn)?shù)的和，但由于結(jié)果太大了，所以你只要告訴母牛哥結(jié)果對(duì) 1000000007 取模即可。
輸入描述:
第一行為?n，表示這個(gè)序列長度為?n?(1?<=?n?<=?10^6)。
接下來的一行有?n?個(gè)數(shù)字?a1,?a2,?……?,?an?(1?<=?ai?<=?2?*?10^9)?表示序列的?n?個(gè)數(shù)字。
輸出描述:
一個(gè)非負(fù)整數(shù)，表示結(jié)果對(duì)?1000000007?取模。
示例1
輸入
3 1 2 3
輸出
23
示例2
輸入
2 1 1
輸出
3
?
題解：
這題，用到一個(gè)規(guī)律，集合的所有子集元素乘積之和。
這個(gè)就是
?
但是這題注意的是取模的時(shí)候，（a%p - b%p ）%p? 的時(shí)候一定要 +p，即為（a%p - b%p + p）%p。
因?yàn)閍%p 之后 可能會(huì)小于b%p 所以相減得到一個(gè)小數(shù)。
一定要記?。。。。。。?！
??
代碼：
#include<iostream>
#include<stdio.h>
using namespace std;
int n;
long long ans=1,ot;
long long oo=1000000007;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
long long a;
scanf("%lld",&a);
ans= (ans%oo * (a+1)%oo )%oo;
}
ot=(ans%oo-1)%oo;
ot=ot%oo;
printf("%lld",ot);
return 0;
}?
?
?
?
嗶哩嗶哩公司福利 424人發(fā)布