解方程
题目描述
解出一元二次方程 (ax+by=c) 的一组整数解 ((x0, y0)) ,使 (left |x_0+y_0 ight |) 最小。
输入格式
共一行，三个整数 (a) , (b) , (c) 。
输出格式
共一行，为 (left |x_0+y_0 ight |) 的最小值。
若无解输出 (“kito”) 。
样例
样例输入 #1
1 1 1
样例输出 #1
1
样例输入 #2
2 3 1
样例输出 #2
0
数据范围与提示
有 (30\%) 的数据，(a,b) 均为质数,(c=1) 。
另有 (20\%) 的数据，(a,b,c) 均为质数。
(100\%) 的数据，(a,b,cleq 1,000,000,000) 。
思路
当时考试以为是个大数论，直接跳过，拿了特判 (10opts) 走人。
其实思路很简单，(x,y) 只能是整数，推一下式子就行了。
设(left |x_0+y_0 ight |=i)
( herefore x=i-y) 或 (x=-i-y)
( herefore y=frac {cpm a*i} {b-a})
这样只需枚举 (i) ，并判断求出来的 (y) 是不是整数即可。
注意要特判一下 (b==a) ，不然会出错。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e9+50;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int a,b,c;
signed main(){
a=read(),b=read(),c=read();
if(c==0){//加这个会更快一丢丢
printf("0
");
return 0;
}
if(a==b){//特判a==b
if(c%a==0){
printf("%lld
",c/a);
}else{
printf("kito
");
}
return 0;
}
for(int i=0;i<=maxn;i++){//枚举i
if((c-a*i)%(b-a)==0){
printf("%lld
",i);
return 0;
}
if((c+a*i)%(b-a)==0){
printf("%lld
",i);
return 0;
}
}
printf("kito
");
return 0;
}
最佳序列
题目描述
你得到了一个 (N) 个非负整数组成的序列 (A) 。
我们称由序列 (A) 的连续若干项组成的新序列为 (A) 的一个连续子序列。给出两个正整数 (L,R(Lleq R)) 。称 (A) 的每一个长度不小于 (L) 且不大于 (R) 的连续子序列为一个纯洁序列，定义纯洁度为纯洁序列的所有元素的平均值。
请你求出所有纯洁序列中的纯洁度的最大值。
输入格式
输入文件的第一行包括 (3) 个正整数 (N,L,R) 。
第二行包括 (N) 个数，按顺序依次表示序列 (A) 的每一项。
输出格式
输出文件包括一行，一个实数，保留 (4) 位小数，表示答案。
样例
样例输入
3 2 3
6 2 8
样例输出
5.3333
数据范围与提示
(20\%) 的数据满足，(1leq Nleq 200) 。
(40\%) 的数据满足，(1leq Nleq 2,000) 。
(100\%) 的数据满足，(1leq Nleq 20,000) , (1leq Lleq Rleq N) , (0leq A_ileq 1,000,000) 。
思路
当时考试的时候想出了 (3) 种方法：
-
(n^3)的暴力，(20,000) 肯定会爆。
-
在上面的基础上用前缀和优化一下，直接压到 (n^2) 。
-
用单调队列来维护，二分查找答案，直接压倒 (nlog_n)，
但是我考试的时候写炸了。
代码
法二暴力
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e4+50;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,l,r;
int a[maxn],sum[maxn];
double ans;
int main(){
n=read(),l=read(),r=read();
for(register int i=1;i<=n;i++){
a[i]=read();
sum[i]=sum[i-1]+a[i];
}
for(register int d=l;d<=r;d++){//register优化一下
int now=0;
for(register int i=1,j;(j=i+d-1)<=n;i++){
now=max(now,sum[j]-sum[i-1]);//除法会比较慢，所以求出和的最大，再进行除法，会很快
}
ans=max(ans,(double)now/d);
}
printf("%.4lf
",ans);
return 0;
}
法三（借用一手大佬的码）
#include <bits/stdc++.h>
using namespace std;
const int maxn=20000+10;
int l,r,n;
int a[maxn];
double tmp[maxn];
double sum[maxn];
int qu[maxn];
bool pd(double x){
for(int i=1;i<=n;i++){
tmp[i]=(double)a[i]-x;
sum[i]=sum[i-1]+tmp[i];
}
int head=1,tail=0;
int now=0;
double ans=-1e9;
for(int i=1;i<=n;i++){
while(i-now>=l){
while(head<=tail&&sum[qu[tail]]>=sum[now]){
tail--;
}
qu[++tail]=now;
now++;
}
while(head<=tail&&i-qu[head]>r){
head++;
}
if(head<=tail){
ans=max(ans,sum[i]-sum[qu[head]]);
}
}
return ans>=0;
}
int main(){
scanf("%d%d%d",&n,&l,&r);
double fl=0,fr;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
fr=max(fr,(double)a[i]);
}
while(fr-fl>=1e-5){
double mid=(fl+fr)/2;
if(pd(mid)){
fl=mid;
}else{
fr=mid;
}
}
printf("%.4lf",(fl+fr)/2);
return 0;
}
周期串查询
题目描述
有一个串只包含数字字符。串的长度为 (n) ，下标从 (1) 开始。
有两种操作方式：
(1,l,r,c) ((1leq lleq rleq n) , (c) 是数字字符)，表示将 (l) 到 (r) 这一段的字符全部改成c字符；
(2,l,r,d) ((1leq lleq rleq n) , (1leq dleq r-l+1))，表示询问 (l) 到 (r) 这一段区间内的子串是否是以d为周期的串。
字符串 (s) 是以 (x) ((1leq xleq left |s ight |)) ,为周期的串的条件是：对于所有的 (i) 从 (1) 到(left |s ight |-x) ， (s_i = s_i + x) 都成立。
输入格式
单组测试数据。
第一行有两个整数(n, m ,k (1leq nleq 10^5, 1leq m+kleq 10^5))，表示字符串长度和修改次数和询问次数。
第二行给出原始的串包含 (n) 位数字字符。
接下来 (m+k) 行，每行一个操作。
有两种形式：
(1,l,r,с) ((1leq lleq rleq n) , (c) 是数字字符)；
(2,l,r,d) ((1leq lleq rleq n) , (1leq dleq r-l+1))。
输出格式
对于每一个询问，如果该段子串是以 (d) 为周期的，输出 (YES) ，否则输出 (NO) 。
样例
样例输入
3 1 2
112
2 2 3 1
1 1 3 8
2 1 2 1
样例输出
NO
YES
数据范围与提示
在这个样例中第一个询问的时候子串是“ (12) ”，他不是以 (1) 为周期的，所以答案是 (NO) 。第二个询问的时候子串是“ (88) ”，是以 (1) 为周期的，所以答案是 (YES) 。
思路
(hash) 线段树的老板子了，但是 (memset+memcmp) 也能卡过，而且还不好卡，正解线段树反而更慢。
代码
memset+memcmp
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+50,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,m,k;
char a[maxn];
int main(){
n=read(),m=read(),k=read();
scanf("%s",a+1);
for(int i=1;i<=m+k;i++){
int opt=read(),l=read(),r=read(),x=read();
if(opt==1){
memset(a+l,x+'0',r-l+1);
}else{
if(memcmp(a+l,a+l+x,r-l-x+1)){
puts("NO");
}else{
puts("YES");
}
}
}
return 0;
}
hash
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxn=2e7+50,mod=1e9+9,base=17;
inline int read(){
int x=0,w=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,m;
char s[maxn];
int a[maxn],b[maxn];
struct Node{
int l,r,lazy;
int hash;
}node[maxn];
void Pushup(int x){
node[x].hash=((node[x<<1].hash*a[node[x<<1|1].r-node[x<<1|1].l+1]+node[x<<1|1].hash)%mod+mod)%mod;
}
void Pushdown(int x){
if(node[x].lazy+1){
node[x<<1].lazy=node[x<<1|1].lazy=node[x].lazy;
node[x<<1].hash=b[node[x<<1].r-node[x<<1].l]*node[x].lazy%mod;
node[x<<1|1].hash=b[node[x<<1|1].r-node[x<<1|1].l]*node[x].lazy%mod;
node[x].lazy=-1;
}
return;
}
void Build(int rt,int l,int r){
node[rt].l=l;
node[rt].r=r;
node[rt].lazy=-1;
if(l==r){
node[rt].hash=s[l]-'0'+1;
return;
}
int mid=(node[rt].l+node[rt].r)>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Add(int rt,int l,int r,int w){
if(node[rt].l==l&&node[rt].r==r){
node[rt].lazy=w;
node[rt].hash=b[node[rt].r-node[rt].l]*w%mod;
return;
}
Pushdown(rt);
int mid=(node[rt].l+node[rt].r)>>1;
if(mid>=r){
Add(rt<<1,l,r,w);
}else if(l>mid){
Add(rt<<1|1,l,r,w);
}else{
Add(rt<<1,l,mid,w);
Add(rt<<1|1,mid+1,r,w);
}
Pushup(rt);
}
int Query(int rt,int l,int r){
if(l>r)return 0;
if(node[rt].l==l&&node[rt].r==r){
return node[rt].hash;
}
Pushdown(rt);
int mid=(node[rt].l+node[rt].r)>>1;
if(mid>=r){
return Query(rt<<1,l,r);
}else if(mid<l){
return Query(rt<<1|1,l,r);
}else {
return (Query(rt<<1,l,mid)*a[r-mid]+Query(rt<<1|1,mid+1,r))%mod;
}
}
signed main(){
n=read();m=read();
scanf("%s",s+1);
a[0]=1;
b[0]=1;
for(int i=1;i<=n;i++){
a[i]=a[i-1]*base%mod;
b[i]=(b[i-1]*base+1)%mod;
}
Build(1,1,n);
while(m--){
int pd=read(),l=read(),r=read(),x=read();
if(pd==1){
Add(1,l,r,x+1);
}else{
if(Query(1,l,r-x)==Query(1,l+x,r)){
printf("YES
");
}else{
printf("NO
");
}
}
}
return 0;
}
追捕
题目描述
(Duan2baka) ：“(jmsyzsfq) 天下第一蠢！”
(jmsyzsfq) ：“你说什么？！”
于是 (Duan2baka) 开始了逃亡的旅程，而 (jmsyzsfq) 也开始追捕 (Duan2baka) 。
他们来到了一个有 (n) 个节点的有向图，迅速逃跑的 (Duan2baka) 会首先降落在有向图的某个节点T上，因为怕发出声音，他会永远静止不动。而随后跟来的 (jmsyzsfq) 会降落在图上随机一个节点 (S) 上（可以与 (T) 相同），并可以沿着图中的有向边随意走动。
因为 (jmsyzsfq) 有着敏锐的嗅觉而且绝顶聪明，他一定会沿着正确的方向寻找 (Duan2baka) 。你可以认为，如果图中存在一条合法的从 (S) 到 (T) 的路径，那么 (jmsyzsfq) 一定会抓到 (Duan2baka) ——因此 (jmsyzsfq) 能否追捕到 (Duan2baka) 在他刚刚降落在图上的时候就已经确定了。
现在请你帮帮 (jmsyzsfq) ，在他降落前告诉他有多大的概率能够追捕到 (Duan2baka) ，并告诉他想要追到 (Duan2baka) 他可以降落在哪些节点上。
输入格式
输入第一行包含三个整数(n) ， (m) ， (opt) ，表示图中有 (n) 个节点，(m) 条有向边；(opt) 为 (0) 或 (1) ，含义见输出格式所述。
输入第 (2) 至 (m+1) 行每行两个整数 (u) ，(v) 描述了图中一条从 (u) 到 (v) 的有向边。
输入第 (m+2) 行一个整数 (T) 表示 (Duan2baka) 降落的位置。
输出格式
如果输入的 (opt) 为 (0) ，只需要输出 (jmsyzsfq) 能够追捕到 (Duan2baka) 的概率。
如果输入的 (opt) 为 (1) ，输出两行，第一行输出 (jmsyzsfq) 能够追捕到 (Duan2baka) 的概率；第二行按从小到大输出想要追到 (Duan2baka) 他可以降落的节点编号，编号间用空格隔开。
对于 (jmsyzsfq) 能够追捕到 (Duan2baka) 的概率，是一个既约分数，形如“ (a/b) ”（(a，b) 为整数），使 (gcd(a,b)=1) ，如果 (a=b) ,输出 (1/1) 。
样例
样例输入 #1
9 10 1
1 2
2 1
2 4
6 1
9 6
6 5
5 3
3 7
3 1
1 8
1
样例输出 #1
2/3
1 2 3 5 6 9
样例 #1解释
图中共 (9) 个节点，能够到达节点 (S=1) 的节点共 (6) 个：({1,2,3,5,6,9}) 。所以能够追捕到 (Duan2baka) 的概率为 (6/9=2/3) 。
样例输入 #2
5 7 1
1 2
1 3
1 5
2 4
4 1
4 5
5 3
1
样例输出 #2
3/5
1 2 4
数据范围与提示
(opt=0) 和 (opt=1) 的数据各 (50\%) 。
对于 (opt=0) 和 (opt=1) 的情况，有着完全相同的子任务：
对于 (10\%) 的数据，(n,mleq 100) 。
对于另外 (30\%) 的数据，(n,mleq 100,000) 。
对于另外 (10%) 的数据，保证图是一个完全图，即对于任意两个点 (u) 和 (v) ，必然有两条有向边 (u→v) 和 (v→u) 。
对于另外 (20\%) 的数据，保证图是一个有向无环图，即对于任意一个点 (x) ，不存在图上一条路径从 (x) 经过其它点后回到 (x) 。
对于另外 (20%) 的数据，保证如果图上存在一条边 (u→v) ，一定存在一条边 (v→u) 。
对于 (100\%) 的数据，(n,mleq 1,000,000) ，保证数据合法且不存在重边、自环。
思路
裸的 (DFS) ，根本没有思路可言，反向建边，反向跑一遍 (DFS) ，这不是有手就行？？？
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+50,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,m,opt,s;
int ans;
int vis[maxn];
int path[maxn];
struct Edge{
int to,next;
}e[maxn];
int GCD(int a,int b){
return b==0 ? a : GCD(b,a%b);
}
int tot,head[maxn];
void Add(int u,int v){
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
}
void DFS(int u){
vis[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(vis[v])continue;
vis[v]=1;
DFS(v);
}
}
int main(){
n=read(),m=read(),opt=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read();
Add(v,u);//反向建边
}
s=read();
DFS(s);//从终点往其他方向跑
for(int i=1;i<=n;i++){
if(vis[i]){
path[++ans]=i;
}
}
int chu=GCD(ans,n);
if(chu!=1){
printf("%d/%d",ans/chu,n/chu);
}else{
printf("%d/%d",ans,n);
}
if(opt==1){
printf("
");
for(register int i=1;i<=ans;i++){
printf("%d ",path[i]);
}
printf("
");
}
return 0;
}
不等式
题目描述
小 (z) 热衷于数学。
今天数学课的内容是解不等式： (Lleq S imes xleq R) 。
小z心想这也太简单了，不禁陷入了深深的思考：假如已知 (L,R,S,M) ，满足 (Lleq (S imes x)mod Mleq R) 的最小正整数该怎么求呢？
输入格式
第一行包含一个整数 (T) ，表示数据组数，接下来是 (T) 行，每行为四个正整数 (M,S,L,R) 。
输出格式
对于每组数据，输出满足要求的 (x) 值，若不存在，输出 (-1) 。
样例
样例输入
1
5 4 2 3
样例输出
2
数据范围与提示
(30\%) 的数据中保证有解并且答案小于等于 (10^6)；
另外 (20\%) 的数据中保证 (L=R)；
(100\%) 的数据中 (Tleq 100,M,S,L,Rleq 10^9)。
思路
首先我们将原式 (Lleq (S imes x)mod Mleq R) 转化成两种式子：
- (Lleq S imes xleq R)
直接求解左边的最小值，即(x=left lceil frac{L}{S} ight ceil)，判断一下是否满足 (S imes xleq R) ，否则无解。
- (Lleq S imes x-M imes yleq R)（(y) 为新的未知数）
移项可得 (S imes x-Rleq M imes yleq S imes x-L)
很明显 (x) 和 (y) 是同增同减的，所以将 (y) 设为我们的主元（主要要求的未知数）。
式子可以变成：
(-R : mod : Sleq M imes y : mod : Sleq -L : mod : S) （(L) 和 (R) 会在一个 (S) 范围内，所以可以直接取模）
再定义：
(L'=-R : mod : S,R'=-L : mod : S)
(S'=M : mod : S,M'=S)
然后我们再递归求解：
- (L+M imes yleq S imes xleq R+M imes y)
当两端点很接近时，会有：
(x=left lceil frac{L+M imes y}{S} ight ceil=left lfloor frac{R+M imes y}{S} ight floor)
所以当 (y) 存在时，就会存在一个解 (x) 。
所以我们每次递归的时候，将区间缩小：
原区间为 ([L,R]) ，宽度为 (R-L+1) 。
缩小后的区间为 ([L',R']) ，宽度为：
(R'-L'+1=(-L\%S+S)\%S-(-R\%S+S)\%S+1=(R-L)\%S+1leq R-L+1)
直到区间小到只有唯一解时，并且在满足没有超出区间范围的情况下，求出唯一解。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int T;
int m,s,l,r;
int Solve(int m,int s,int l,int r){
if(r>=m) r=m-1;//防止取模后为0
if(l>r||m<=l) return -1;//无解的情况
s%=m;
int ans=(l-1)/s+1;//求出第一种情况的解
if(ans*s<=r){//没有超出右端点
return ans;
}
int a=(-r%s+s)%s;//缩小范围
int b=(-l%s+s)%s;
int y=Solve(s,m,a,b);//向下递归
if(y==-1)return -1;//无解
int x=(r+m*y)/s;//其实用左边求值，判断是否超出右边界，也是一样
if(l<=s*x-m*y){
return x;
}
return -1;//剩下都是无解
}
signed main(){
T=read();
while(T--){
m=read(),s=read(),l=read(),r=read();
printf("%lld
",Solve(m,s,l,r));
}
return 0;
}