头像

acwing_zyy

$\color{Red}{AcWing\, University}$




离线:4小时前


最近来访(134)
用户头像
牛蛙点点
用户头像
Frosterosion
用户头像
正_函数
用户头像
Vanish_7
用户头像
sjzezli
用户头像
zwling
用户头像
ε_1
用户头像
赵洵
用户头像
彬腾
用户头像
yzxyxyx
用户头像
五星市民欧某人
用户头像
不想罚座
用户头像
Elpsy_3
用户头像
福尔摩东
用户头像
Arthur_5
用户头像
AnotherLongMarch
用户头像
Java的神秘男友script
用户头像
杲析
用户头像
Janisa
用户头像
心升明月


acwing_zyy
22小时前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int cnt=0,res;
    void dfs(TreeNode* root,int k)
    {
        if(!root)return ;
        dfs(root->left,k);
        cnt++;
        if(cnt==k)
        {
            res=root->val;
            return ;
        }
        dfs(root->right,k);
    }
    int kthSmallest(TreeNode* root, int k) {
        dfs(root,k);
        return res;
    }
};


分享 备忘录

acwing_zyy
22小时前
1.孙庞猜数
2.周赛题解
3.费用背包



acwing_zyy
22小时前
class Solution {
public:
    inline bool isop(string &s)
    {
        if(s=="+"||s=="-"||s=="*"||s=="/")return true;
        return false;
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        for(string &s:tokens)
        {
            if(isop(s))
            {
                int num2=stk.top();
                stk.pop();
                int num1=stk.top();
                stk.pop();
                int res;
                if(s=="+")res=num1+num2;
                else if(s=="-")res=num1-num2;
                else if(s=="*")res=num1*num2;
                else
                    res=num1/num2;
                stk.push(res);
            }
            else
                stk.push(atoi(s.c_str()));
        }
        return stk.top();
    }
};



4080. 第k个数

给定一个 $n×m$ 的方格矩阵,每个方格内都有一个整数元素。

其中第 $i$ 行第 $j$ 列的方格中的元素为 $i×j$(行和列都从 $1$ 开始编号)。

现在,需要你将这 $n×m$ 个整数按照非严格单调递增的顺序一一写出。

请问,你写出的第 $k$ 个整数是多少。

输入格式

一行,三个整数 $n,m,k$。

输出格式

一行,输出你写出的第 $k$ 个整数。

数据范围

前 $6$ 个测试点满足 $1≤n,m≤10$。
所有测试点满足 $1≤n,m≤5×10^5$,$1≤k≤n×m$。

输入样例1:

2 2 2

输出样例1:

2

输入样例2:

2 3 4

输出样例2:

3

输入样例3:

1 10 5

输出样例3:

5

解题思路

二分

二分答案,要求判断当前数在所有数中的排名,即:找有多少个数比当前数小,按行枚举,从第一行开始,找出其在第一行中的排名,假设找到该位置,由于该列小于下一行的对应列,所以当前数在下一行的排名只会在前面,即从上往下时当前数的排名只会往前。这样就能在 $O(n+m)$ 的复杂度内找出当前数的排名,接着二分即可~

  • 时间复杂度:$O((n+m)\times log(nm))$

代码

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int n,m;
LL k;
bool ck(LL x)
{
    int j=m;
    LL s=0;
    for(int i=1;i<=n;i++)
    {
        while(j&&1ll*i*j>x)j--;
        s+=j;
    }
    return s>=k;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&k);
    LL l=1,r=1ll*n*m,res;
    while(l<=r)
    {
        LL mid=l+r>>1ll;
        if(ck(mid))
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%lld",res);
    return 0;
}


活动打卡代码 AcWing 1283. 玄武密码

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N=3e7+10;
int get(char c){
    if(c=='N') return 0;
    if(c=='E') return 1;
    if(c=='W') return 2;
    return 3;
}
char s[N];
int n,m,tt=1,last=1;
struct node {
    int len,fa;
    int ch[4];
}tr[N];
void extend(int c){
    int p=last,np=last=++tt;
    tr[np].len=tr[p].len+1;
    for(;p&&!tr[p].ch[c];p=tr[p].fa) tr[p].ch[c]=np;
    if(!p) tr[np].fa=1;
    else {
        int q=tr[p].ch[c];
        if(tr[q].len==tr[p].len+1) tr[np].fa=q;
        else {
            int nq=++tt;
            tr[nq]=tr[q];tr[nq].len=tr[p].len+1;
            tr[q].fa=tr[np].fa=nq;
            for(;p&&tr[p].ch[c]==q;p=tr[p].fa) tr[p].ch[c]=nq;
        }
    }
}
int main()
{
    cin>>n>>m;
    scanf("%s",s);
    for(int i=0;s[i];i++) extend(get(s[i]));
    while(m--){
        scanf("%s",s);
        int p=1,res=0;
        for(int i=0;s[i];i++){
            int c=get(s[i]);
            if(tr[p].ch[c]) p=tr[p].ch[c],res++;
            else break;
        }
        printf("%d\n",res);
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2766. 后缀自动机

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+10;
int tt=1,last=1;
struct node {
    int len,fa;
    int ch[26];
}tr[N];
char s[N];
int f[N];
void extend(int c){
    int p=last,np=last=++tt;
    f[tt]++;
    tr[np].len=tr[p].len+1;
    for(;p&&!tr[p].ch[c];p=tr[p].fa) tr[p].ch[c]=np;
    if(!p) tr[np].fa=1;
    else {
        int q=tr[p].ch[c];
        if(tr[q].len==tr[p].len+1) tr[np].fa=q;
        else {
            int nq=++tt;
            tr[nq]=tr[q];tr[nq].len=tr[p].len+1;
            tr[q].fa=tr[np].fa=nq;
            for(;p&&tr[p].ch[c]==q;p=tr[p].fa) tr[p].ch[c]=nq;
        }
    }
}
int head[N],ver[N],ne[N],ind;
void add(int x,int y){
    ver[++ind]=y;ne[ind]=head[x];head[x]=ind;
}
ll ans;
void dfs(int u){
    for(int i=head[u];i;i=ne[i]){
        int y=ver[i];
        dfs(y);
        f[u]+=f[y];
    }
    if(f[u]>1)
    ans=max(ans,1ll*f[u]*tr[u].len);
}
int main()
{
    scanf("%s",s);
    for(int i=0;s[i];i++) extend(s[i]-'a');
    for(int i=2;i<=tt;i++){
        add(tr[i].fa,i);
    }
    dfs(1);
    cout<<ans<<'\n';
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



  • lower_bound
int find(vector<int> &a,int val)//lower_bound
{
    int l=0,r=a.size()-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(a[mid]<val)l=mid+1;
        else 
            r=mid-1;
    }
    return l;
}
  • upper_bound
int find(vector<int> &a,int val)//upper_bound
{
    int l=0,r=a.size()-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(a[mid]<=val)l=mid+1;
        else 
            r=mid-1;
    }
    return l;
}



  • 时间复杂度:$O(logn)$
long long nthPalindrome(long long n)
{
    long long cnt=0,num=9;
    int x=0;
    while(true)
    {
        if(x>0&&x%2==0)num*=10;
        x++;
        if(cnt+num>n)break;
        cnt+=num;
    }
    n-=cnt;
    int h=1;
    for(int i=0;i<(x-1)/2;i++)h*=10;
    int half=h+n;
    long long res=half;
    if(x&1)half/=10;
    while(half)
    {
        res=res*10+half%10;
        half/=10;
    }
    return res;
}



  • 时间复杂度:$O(logn)$
long long nextPalindrome(long long num)
{
    string s=to_string(num);
    int n=s.size();
    for(int i=n/2;~i;i--)
        if(s[i]!='9')
        {
            s[i]++;
            if(n-i-1!=i)s[n-i-1]++;
            for(int j=i+1;j<=n/2;j++)
            {
                s[j]='0';
                s[n-j-1]='0';
            }
            return stoll(s);
        }
    long long res=1;
    for(int i=0;i<n;i++)res*=10;
    res++;
    return res;
}


活动打卡代码 LeetCode 342. 4的幂

  • 模拟
class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<=0)return false;
        while(n%4==0)n/=4;
        return n==1;
    }
};
  • 二进制
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n>0&&(n&(n-1))==0&&(n&0xaaaaaaaa)==0;
    }
};