首页 > 其他分享 >ACM第三次测试部分题解(B,C,D,E,J)

ACM第三次测试部分题解(B,C,D,E,J)

时间:2024-08-03 11:08:26浏览次数:13  
标签:ch return 第三次 int 题解 LL ACM long include

(B)N^N (简单快速幂模板,直接套用就行)

点击查看代码
#include<iostream>
using namespace std;
long long a, b,n;
 
int main()
{
    cin >> n;
    while(n--)
    {
        scanf("%lld", &a);
        signed long long A = a%10,sum=1;
        while (a)
        {
            if (a & 1) sum = A*sum%10;
            A = A*A%10;
            a >>= 1;
        }
        cout << (sum + 10)%10;
        cout << endl;
    }
    return 0;
}
(C)后缀表达式
点击查看代码
#include<iostream>
#include<cstring> 
#include<stack> 
using namespace std;
string s;
stack<char> a;

bool isoperator(char ch)
{
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ')' || ch == '(')
        return true;
    else
        return false;

}

int getpre(char ch, bool flag)  //按照运算顺序分级
{
    if (ch == '+' || ch == '-')
        return 1;
    if (ch == '*' || ch == '/')
        return 2;
    if (ch == '(' && flag)
        return 0;
    if (ch == '(' && !flag)
        return 3;
}

int main()
{
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (!isoperator(s[i]))
        {
            cout << s[i];
            continue;
        }
        else
        {
            if (a.empty())
            {
                a.push(s[i]);
                continue;
            }
            else
            {
                if (s[i] == ')')
                {
                    while (a.top() != '(' && !a.empty())  // 遇到 )将( 前所有元素输出,再删除(
                    {
                        cout << a.top();
                        a.pop();
                    }
                    a.pop();
                    continue;
                }
                while (!a.empty() && getpre(s[i], 0) <= getpre(a.top(), 1))
                {
                    cout << a.top();
                    a.pop();
                }
                a.push(s[i]);
            }

        }
    }
    while (!a.empty())
    {
        cout << a.top();
        a.pop();
    }
    return 0;
}

(D)KMP字符串模式匹配算法实现 (也是一个模板直接用,代码可以找视频慢慢理解,原理很简单)
点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 11;
int next1[N],n,m;
char p[N],s[N];
  
void ne()
{
    next1[1] = 0;  //存储串中最长前后缀长度
    for (int i = 2, j = 0; i <= n; i++)  // i扫描串,j扫描前缀
    {
        while (j && p[i] != p[j + 1]) //从1开始存所以加1
            j = next1[j];//回跳前一位
        //遍历串,当i与j+1为不同时,j 跳至匹配位置,若无跳至0
        if (p[i] == p[j + 1]) j++; //相等时J++,指向前缀末尾
        next1[i] = j;
    }
}
  
int pi()
{
    for (int i = 1, j = 0; i <= m; i++)  //遍历主串
    {
        while (j && s[i] != p[j + 1]) j = next1[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n) //前缀与字串长度一致时,找到位置
        {
            printf("%d\n", i - n + 1);
            return 0;
            //j=next1[j];  //重新寻找字串
        }
    }
    return 1;
}
  
int main()
{
    for(int i=0;i<3;i++)
    {
        cin >> s + 1 >> p + 1;
        m = strlen(s + 1);
        n = strlen(p + 1);
        ne();
        int k = pi();
        if (k) cout << 0 << endl;
    }
    //for (int i = 1; i <= n; i++)
    //  cout << next1[i] << ' ';
    return 0;
}
(E)同余方程(这题不用long long会超时,其他的就是模板)
点击查看代码
#include<iostream>
using namespace std;
#define LL long long
LL a, b, x, y;
 
LL ex(LL a, LL b, LL& x, LL& y)
{
    if (!b)
    {
        x = 1; y = 0; 
        return a;
    }
    LL r = ex(b, a % b, y, x);
    y -= a / b * x;
    return r;
}
 
int main()
{
    cin >> a >> b;
    ex(a, b, x, y);
    cout << (x % b+b)%b;
    return 0;
}
(J)跳房子(这题有难度,大家可以看看代码理解思路)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
  
const int Max=500005;
int n,m,k,d,head,tail,l,r,mid,maxlen,minlen,now,tag;
int x[Max],num[Max],f[Max],p[Max];
  
inline int get_int()
{
    int x=0,f=1;
    char c;
    for(c=getchar();(!isdigit(c))&&(c!='-');
    c=getchar());
    if(c=='-') 
    f=-1,c=getchar();
    for(;isdigit(c);c=getchar()) 
    x=(x<<3)+(x<<1)+c-'0';
    return x*f;
}
  
inline bool check(int len)
{
    now=0,head=1,tail=0,maxlen=len+d,minlen=max(d-len,1);
    for(int i=1;i<=n;i++)
    {
      while(x[now]<=x[i]-minlen)
      {
        if(f[now]<=-1e9)
        {
            now++;
            continue;
            
        }   //不能到达now 
        while(head<=tail&&f[now]>=f[p[tail]]) 
        tail--;
        p[++tail]=now,now++;   //放进队列 
      }
      while(head<=tail&&x[p[head]]<x[i]-maxlen) 
      head++;
      if(head<=tail) 
      f[i]=f[p[head]]+num[i];
      else 
      f[i]=-1e9;
      if(f[i]>=k) 
      return 1;  //有满足的直接返回 
    }
    return 0;
}
  
int main()
{
    n=get_int(),d=get_int(),k=get_int();
    for(int i=1;i<=n;i++)
    x[i]=get_int(),num[i]=get_int();
    l=0,r=500000;
    while(l<r)  //二分答案 
    {
      mid=(l+r)>>1;
      if(check(mid)) tag=1,r=mid;
      else l=mid+1;
    }
    if(tag) 
    cout<<r;
    else
    cout<<"-1\n";
    return 0;
}

标签:ch,return,第三次,int,题解,LL,ACM,long,include
From: https://www.cnblogs.com/liyutaocpp/p/18340182

相关文章

  • AGC039B 题解
    因为一条边只能在\(V_i,V_i+1\)之间,如果把\(V_1,V_3,\cdots\)看作一部分,\(V_2,V_4,\cdots\)看作一部分,这就是个二分图。考虑一个二分图怎么“展开”成最多的集合。考虑答案上界。上界是点对最短路的最大值加一。如果集合个数超过上界,那么一定存在一条边跨越多个集合。猜......
  • AGC033C 题解
    这里树的直径\(l\)定义为两个有硬币的点的最长距离。做一次操作后,树的直径一定会变短。我们发现,如果在直径端点做操作,直径减一。在非直径端点操作,直径减二。于是变成了一个威佐夫博弈,但是要注意的是,在直径长度为0,1,2的时候,每次都只能让直径减一。因为直径长度为1,先手必......
  • AGC059B 题解
    对于一种构造,考虑怎么表示。可以把相邻不同颜色建图连边。注意到答案不可能小于\(n-1\),否则图不联通,显然不可能。考虑什么情况下是\(n-1\)。图是一棵树。考虑怎么构造出一棵树。因为一种颜色出现次数大于等于这个点的度数,可以考虑可以确定叶子。把剩余度数最小的往最大的......
  • AGC056A 题解
    首先考虑\(n\equiv0\pmod3\)的情况。非常简单,然后考虑\(n\equiv1\pmod3\)的情况。只要把多出来的第一列第一行填满就行了。还要比原来情况多一个连通块。然后考虑\(n\equiv2\pmod3\)的情况。手玩一下,再往左上角添一点东西就行了。#include<bits/stdc++.h>us......
  • AGC044B 题解
    考虑每次更新就跑一遍bfs。\(O(n^4)\),复杂度不对?但是注意到\(dis\)的最大值也就是\(n\),每次更新\(dis\)至少减一。所以最大值最多被更新\(n\)次,一共更新\(O(n^3)\)次,复杂度是对的。直接暴力。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;......
  • ABC267F 题解
    注意到,对于一棵树\(T\)的任一直径\(a-b\),对于任意一点\(u\),离\(u\)最远的点一定是\(a\)或\(b\)。考虑反证:如图,如果存在点\(c\)使得\(dis(u,c)>\max(dis(u,a),dis(u,b))\)。如图,\(a-b\)为直径,\(d2>d1\)。因为有\(d4>d3+d2\),所以有\(d2+d3+d4>2d2+2d3>d1+d2\),所以......
  • ABC266F 题解
    输入的图是一颗基环树。对于\(x,y\),如果把环上的边去掉,得到的森林里\(x,y\)仍然在同一颗树内,那么显然只有一条路。否则一定要经过环,有两条路。于是dfs或着拓扑排序找环即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e5+......
  • 2024集训8.2模拟赛题解
    考试历程8:30开始考试8:40快速浏览了T1并想了一下,是一道质数的题目,准备打表,打到一半的时候发现空间复杂度会爆,于是改打质数筛暴力了9:30打完T1开始看T2刚开始没思路,先看了T3,跟着样例打了一点,估计可以拿点分吧9:50打完了T3会看T2发现了一点规律(后来知道是错的)跟着思路写了一......
  • gym105167E Erdős-Ginzburg-Ziv 题解
    题意:给\(p\)和\(p-1\)个边权,要用这些边权构造树,每个点编号\(0\simp-1\),使得每个点\(u\)到\(0\)的距离\(\bmod\p=u\),无解输出-1,保证\(p\)是质数、\(p\le10^6\)、边权\(\in[1..p-1]\).Solution考虑加边的过程,树最开始只有根节点0,然后通过加边不断地引入新的点......
  • 优秀的树 - 题解(数学)
    优秀的树时间限制:C/C++2000MS,其他语言4000MS内存限制:C/C++256MB,其他语言512MB描述给定一棵树,其所有边权重均为\(1\),定义\(f(u)=Σ_vdis(u,v)\),v表示树上的所有结点,\(dis(u,v)\)表示结点\(u\)和\(v\)的简单路径的长度。一棵树被称为“优秀”,当且仅当存在两个......