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 我们一起讨论
各路神犇各位大佬请多多指教！