Problem A 序列
題目描述
對于一個給定的非負序列 { a 1 , a 2 , … , a n } ， \{ a_1,a_2,…,a_n\}， {a1,a2,…,an}，我們稱在 1 ≤ i , j ≤ n 1≤i,j≤n 1≤i,j≤n時滿足 k ⋅ ∣ i − j ∣ ≤ m i n { a i , a j } k⋅|i−j|≤min\{a_i,a_j\} k⋅∣i−j∣≤min{ai,aj}的 k k k為這個序列的擴張指數。你的任務就是對于某個序列求出它的擴張指數。資料保障一定存在一個擴張指數。
輸入
輸入的第一行為一個正整數 n n n，代表這個序列元素的個數。
輸入的第二行為 n n n個正整數，代表該序列某位置上元素的值。
輸出
輸入的第一行為一個正整數k，代表這個序列的擴張指數。
樣例輸入
【樣例 1 1 1】
4 4 4
6 6 6 4 4 4 5 5 5 5 5 5
【樣例 2 2 2】
4 4 4
821 821 821 500 500 500 479 479 479 717 717 717
樣例輸出
【樣例 1 1 1】
1 1 1
【樣例 2 2 2】
239 239 239
提示
對于 30 % 30\% 30%的資料滿足 n ≤ 1000 n≤1000 n≤1000。
對于另外 10 % 10\% 10%的資料滿足序列中數字全部相同。
對于 100 % 100\% 100%的資料滿足 n ≤ 300000 n≤300000 n≤300000。
S o l u t i o n : Solution: Solution:
原式 k ⋅ ∣ i − j ∣ ≤ m i n { a i , a j } k⋅|i−j|≤min\{a_i,a_j\} k⋅∣i−j∣≤min{ai,aj}可化為:
k ≤ m i n { a i , a j } ∣ i − j ∣ k≤\frac{min\{a_i,a_j\}}{|i−j|} k≤∣i−j∣min{ai,aj}
當 i i i和 j j j距離越大，不等式右邊越小，對答案就越有價值
考慮每個數對于答案的貢獻：隻有這個數是兩個數中最小的才會對答案有貢獻。但如果是兩個數中最大的，因為最小的也會算一遍，是以取個 m i n min min對答案就沒有影響咯。
最後其實就一句話:枚舉每個數，每次取它距離左端點和右端點最大的做比
上我短小精悍的代碼:
#include<bits/stdc++.h>
using namespace std;
int n,x,ans=0x7f7f7f7f;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
ans=min(ans,x/max(i-1,n-i));
}
printf("%d\n",ans);
}
Problem B 字母島
題目描述
S F q q q SFqqq SFqqq在上一次擷取了地圖以後，發現地圖上有一個群島，于是他決定前去探險。我們知道這個群島是由 n n n個小島構成的，對于每個島嶼上面都存在着一個字母。島嶼之間有 m m m條有向邊，對于一個路徑的得分為所經過的字母出現最頻繁的一個出現的次數。
S F q q q SFqqq SFqqq想要得到盡可能高的分，他當然知道怎麼做啦，隻是想考考你。
輸入
輸入的第一行為兩個正整數 n , m ， n,m， n,m，代表島嶼和邊的個數。
輸入的第二行為一個長度為 n n n的字元串，每個字元分别代表對應編号島嶼上的字母。
之後的 m m m行輸入，每行兩個數 u ， v u，v u，v。代表從島 u u u至島 v v v有一條邊。
輸出
輸出僅一行，為得分大小。若可以無窮大，則輸出 − 1 -1 −1。
樣例輸入
【樣例 1 1 1】
5 5 5 4 4 4
a b a c a abaca abaca
1 1 1 2 2 2
1 1 1 3 3 3
3 3 3 4 4 4
4 4 4 5 5 5
【樣例 2 2 2】
6 6 6 6 6 6
x z y a b c xzyabc xzyabc
1 1 1 2 2 2
3 3 3 1 1 1
2 2 2 3 3 3
5 5 5 4 4 4
4 4 4 3 3 3
6 6 6 4 4 4
樣例輸出
【樣例 1 1 1】
3 3 3
【樣例 2 2 2】
− 1 -1 −1
提示
首先考慮無窮大特殊情況，如果無窮大肯定是因為有一條路徑可以一直走下去，是以我們先判個環。
判過環之後就剩下了一個有向無環圖，我們需要計算每個字母出現的次數
那麼就可以把這個字母代表的節點指派為 1 1 1，剩下的為 0 0 0，然後在圖上跑 d p dp dp。圖上 d p dp dp可以類比成樹上 d p dp dp，用記憶化搜尋就可以實作了。
上代碼 :
#include<bits/stdc++.h>
using namespace std;
#define N 300030
#define reg register
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int to,nxt;
}edge[N];
int n,m,x,y,cnt,ans,in[N],deg[N],dp[N],val[N],dis[N],head[N];
char str[N];
bool vis[N],used[N];
inline void addedge(int u, int v){
edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt;
}
queue<int> q;
bool dfss(){
int tot=0;
for(reg int i=1;i<=n;i++){
if(!in[i])q.push(i),tot++;
vis[i]=1;
}
while(!q.empty()){
int vv=q.front();
q.pop();
for(reg int i=head[vv];i;i=edge[i].nxt){
int now=edge[i].to;
in[now]--;
if(!in[now])vis[now]=1,q.push(now),tot++;
}
}
return tot==n;
}
void dfs(int x){
dp[x]=val[x];
vis[x]=1;
for(reg int i=head[x];i;i=edge[i].nxt){
int vv=edge[i].to;
if(!vis[vv])dfs(vv);
dp[x]=max(dp[x],dp[vv]+val[x]);
}
ans=max(dp[x],ans);
}
int main(){
read(n),read(m);
scanf("%s",str+1);
for(reg int i=1;i<=m;i++)read(x),read(y),addedge(x,y),in[y]++,deg[y]++;
if(!dfss())return printf("-1\n"),0;
for(reg int i=0;i<26;i++){
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
for(reg int j=1;j<=n;j++){
if(str[j]=='a'+i)val[j]=1;
else val[j]=0;
}
for(reg int j=1;j<=n;j++){
if(!deg[j])dfs(j);
}
}
printf("%d\n",ans);
}
Problem C 盡頭
題目描述
有人在這裡收益良多，也有人在這裡失去所有。
給定兩個正整數 a a a， b b b，以及一個其中元素為 1 1 1或 − 1 -1 −1的序列 s s s，其初始下标為 0 0 0。我們已知這個序列是以 k k k為周期的且 k k k能整除 n + 1 n+1 n+1。也可以說是序列中 s i = s i − k s_i=s_i-k si=si−k。
對于這個序列，我們想要知道 ∑ i = 0 n s i a n − i b i \sum_{i=0}^ns_ia^{n-i}b^i ∑i=0nsian−ibi對于 1 e 9 + 9 1e9+9 1e9+9的餘數是多少。
輸入
輸入的第一行為四個正整數 n n n a a a b b b k k k。
輸入的第二行為一個長度為 k k k的字元串，每個字元分别為 ‘ + ’ ‘+’ ‘+’或 ‘ − ’ ‘-’ ‘−’代表着這個位置是 1 1 1或 − 1 -1 −1。
我們隻會給出前 k k k個，其他的數字我們可以通過周期性獲得。
輸出
輸出僅一行，為得數對于 1 e 9 + 9 1e9+9 1e9+9的餘數
樣例輸入
【樣例 1 1 1】
2 2 2 2 2 2 3 3 3 3 3 3
+ − + +-+ +−+
【樣例 2 2 2
4 4 4 1 1 1 5 5 5 1 1 1
− - −
樣例輸出
【樣例 1 1 1】
7 7 7
【樣例 2 2 2】
999999228 999999228 999999228
提示
，
本題由于 s s s是循環的，是以我們從循環入手
注意到當下标 i i i對于 k k k的餘數是一樣的時候， s s s數組的值也是一樣的，并且二者之間相差 ( b a ) k (\frac{b}{a})^k (ab)k倍，是以我們可以直接用等比數列求和來做。
等比數列求和公式:
設數列共有 n n n項，首項為 a 1 a_1 a1，公比為 q q q，那麼等比數列的和為 S n = a 1 1 − q n 1 − q S_n=a_1\frac{1-q^n}{1-q} Sn=a11−q1−qn
是以我們隻需要枚舉 0 − k 0-k 0−k中的數就行了，複雜度 O ( k l o g n ) O(klog_n) O(klogn)
注意:
1. 1. 1.我國小從學這個公式到現在都不知道為什麼要把 1 1 1放前面…寫公式時候這麼寫行，但是寫代碼咱别上頭。
2. 2. 2.這個數列之和是 s i s_i si倍的等比數列和，不要把 s i s_i si乘到 a 1 a_1 a1裡！！！！！！網站上這個可以過但是 c f cf cf上不行！！！！
3. 3. 3.公比為 1 1 1的時候公式炸了，是以公比為 1 1 1時得直接算，就是 s i × a n s_i×a^n si×an
上代碼:
#include<bits/stdc++.h>
using namespace std;
#define N int(1e5+10)
typedef long long ll;
const ll mod=1e9+9;
inline ll quickpow(ll x, ll y){
while(x<0)x+=mod;
ll ret=1;
while(y){
if(y&1)(ret*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return ret;
}
ll n,a,b,k,ans,sum[N],s[N];
char ch;
int main(){
scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
for(ll i=1;i<=k;i++){
ch=getchar();
while(ch!='+'&&ch!='-')ch=getchar();
if(ch=='+')s[i-1]=1;
else s[i-1]=mod-1;
}
for(ll i=0;i<k;i++){
ll a1=quickpow(a,n-i)%mod*quickpow(b,i)%mod;
ll q=quickpow(b,k)*quickpow(quickpow(a,k),mod-2)%mod;
ll nown=(n+1)/k;
if(q==1)(ans+=s[i]*a1%mod*((n+1)/k)%mod)%=mod;
else (ans+=s[i]*(a1*(quickpow(q,nown)-1)%mod*quickpow(q-1,mod-2)%mod)%mod)%=mod;
}
printf("%lld\n",ans);
}
D a y 1 Day1 Day1的考試題就是這樣 ！雖然是打着 D a y 2 Day2 Day2的旗号但是沒什麼難題
有問題可以寫到下面的評論區 或者加 Q Q 407694747 QQ407694747 QQ407694747 我們一起讨論
各路神犇各位大佬請多多指教！