新鲜事 原文

h_s
12分钟前
改了一会bug不知道为啥就改对了(难受)



adorhorriable
21分钟前

切记:int n = strlen(s+1); 要单独拿出来,不然一定会出现TLE。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010,pk=131;
typedef unsigned long long ULL;
ULL h[N],p[N];

char s[N];

ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    scanf("%s",s+1);
    p[0]=1;
    int n = strlen(s+1);
    for(int i=1;i<n;i++)
    {
        h[i]=h[i-1]*pk+(s[i]-'a')+1;
        p[i]=p[i-1]*pk;
    }
    int m,l1,l2,r1,r2;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        ULL u1=get(l1,r1);
        ULL u2=get(l2,r2);
        if(u1==u2) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}



#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define MaxN 55
//#define MOD 998244353
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define endl '\n'
#define LL long long
#define PII pair<int,int>
#define rint register int 
#define ULL unsigned long long
const int MOD=1000000007;
//int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
template<class T> inline void read(T& x){
    x=0;int f=0;char ch=getchar();
    while( !isdigit(ch) ) f|=( ch == '-' ) , ch=getchar();
    while( isdigit(ch) )  x = ( x<<1 ) + ( x<<3 ) + ( ch^48 ) , ch=getchar();
    x = f ? -x : x;
}
template<class T> inline void print(T x){
    if ( x < 0 ) { putchar('-'); x = -x; }
    if ( x >= 10 ) print( x / 10 );
    putchar(x % 10 + '0');
}
int dp[MaxN][MaxN][15][15],val[MaxN][MaxN];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            cin>>val[i][j];
            val[i][j]++;
        }
    dp[1][1][1][val[1][1]]=1;
    dp[1][1][0][0]=1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int u=0; u<=k; u++){
                for(int v=0; v<=13; v++){
                    dp[i][j][u][v]+=(dp[i-1][j][u][v]+dp[i][j-1][u][v])%MOD;
                    if( u > 0 && val[i][j] == v ){
                        for(int c=0; c<v; c++){
                            dp[i][j][u][v]+=(dp[i-1][j][u-1][v]+dp[i][j-1][u-1][v])%MOD;
                        }
                    }
                }
            }
        }
    }
    LL ans=0;
    for(int i=0; i<=13; i++){
        ans=(ans+dp[n][m][k][i])%MOD;
    }
    cout<<ans%MOD<<endl;
    return 0; 
}



新鲜事 原文

AcWing 升级了?



TSNA
1小时前

题目描述

求一个数开三次方的结果,精确到小数点后6位

样例

输入:

1000.00

输出:

10.000000

算法1—浮点数的二分查找—JAVA

就是还是通过二分的思想来做,确定范围,每次去一半,然后check一下是否满足当前条件然后来重新给Lift和Right赋值,直到找到精确到6位的结果。

时间复杂度: $O(nlogn)$

参考文献 y总

JAVA 代码

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static final double FW = 1e-8;
    public static double N = 0;
    public static double bsearch_01(double l, double r){
        while ((r - l) > FW){
            double mid = (l + r) / 2;
            if ((mid * mid * mid) >= N) r = mid;
            else l = mid;
        }
        return l;
    }
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        N = scan.nextDouble();
        if (N < 0){
            N = -N;
            double target = bsearch_01(0, N);
            System.out.println(String.format("%.6f",-target));
        }else {
            double target = bsearch_01(0, N);
            System.out.println(String.format("%.6f",target));
        }

    }
}

注意

  1. 精度
    (1)如何表示精度
    (2)保留6位小数的话,一般设置位1e-8
    (3)String.format(“%.6f”,target); 输出
  2. 负数



Accepting
1小时前

鄙人不才,此中鄙陋甚多,望海涵!!!

这道题目刨析之后就会发现它其实是按照对角线来输出的,在一个n*n的矩阵中,共有2*n+1条对角线,所以我们在读入的时候可以观察每个数的横纵坐标之和来判断它在哪条斜线上,研究后我们就会发现,当横纵坐标之和为偶数的对角线是要从下往上输出,反之是要从上往下输出,这样的话我们不难想到双端队列,可以将偶数的每次push_front(),反之push_back(),最终遍历双端队列去得到结果即可!(注意,其实双端队列的常数复杂度还是比较大的,因此这个方法在代码量上应该是最优的,但在运行时间上还是有点慢,当然也可以手动模拟双端队列,但是由于这道题目的数据少,我们直接利用STL自带双端队列即可)

#include<iostream>
#include<deque>

using namespace std;

const int N=1010;

deque<int> a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            if(!((i+j)&1)) a[i+j].push_front(x);
            else a[i+j].push_back(x);
        }
    for(int i=2;i<=2*n;i++)  for(auto x:a[i]) printf("%d ",x);
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!




Wou
1小时前
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;

LL a, b, x, y;

LL exgcd(LL a, LL b, LL& x, LL& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL gcd = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return gcd;
}

int main()
{
    scanf("%lld%lld", &a, &b);
    LL gcd = exgcd(a, b, x, y);
    x /= gcd;
    b /= gcd;
    printf("%lld", (x%b+b)%b);
    return 0;
}



皓首不倦
1小时前


'''
简单两次二分即可
'''

n, q = map(int, input().split())

arr = list(map(int, input().split()))

for _ in range(q):
    val = int(input())

    l, r = 0, len(arr)-1
    ans1 = -1
    while l <= r:
        mid = l + (r-l) // 2
        if arr[mid] == val:
            ans1 = mid
            r = mid - 1
        elif arr[mid] < val:
            l = mid + 1
        else:
            r = mid - 1

    if ans1 == -1:
        print(-1, -1)
    else:
        ans2 = -1
        l, r = ans1, len(arr)-1
        while l <= r:
            mid = l + (r - l) // 2
            if arr[mid] == val:
                ans2 = mid
                l = mid + 1
            elif arr[mid] < val:
                l = mid + 1
            else:
                r = mid - 1

        print(ans1, ans2)






SXL
1小时前

这道题用到$GCD$,在$AcWing$上过了,但是洛谷$9$个点$RE$

然后发现是$gcd$中产生了$0$,程序除以$0$导致的,但是$AcWing$没有这样的特判数据

(也就是$0/1$的情况)

@yxc请求加强数据




Accepting
1小时前

鄙人不才,此中鄙陋甚多,望海涵!!!

简单标记

#include<iostream>

using namespace std;

const int N=1010;

int a[N];

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        scanf("%d",&x);
        a[x]++;
        printf("%d ",a[x]);
    }
    return 0;
}

持续更新中,更新完历年1,2就会更新4,5!