目录

一.字符串模拟

字符串模拟

二. 高精度计算

1. 回文数（高精度，进制转换）

P1015 回文数
题目描述
若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个十进制数565656，将565656加656565（即把565656从右向左读），得到121121121是一个回文数。又如：对于十进制数878787：STEP1：878787+787878 = 165165165
STEP2：165165165+561561561 = 726726726
STEP3：726726726+627627627 = 135313531353
STEP4：135313531353+353135313531 = 488448844884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一个N(2≤N≤10,N=16)进制数M(100位之内)，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出Impossible!

#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=1e4+500;
const int mod=1e9+7;
using namespace std;
char six[20]="0123456789ABCDEF";//打表16进制
string m;
inline int read()
{
    int f=0,x=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?-x:x;
}
bool cherk(string s)//用reverse函数直接判断回文数
{
    string a=s;
    reverse(a.begin(),a.end());
    return a==s;
}
string add(int n,string b)
{
    string a=b;
    reverse(a.begin(),a.end());//翻转相加
    int numa[maxn],numb[maxn],numc[maxn],tmp=0;
    int len=a.length(),lenc=1;
    string ans;
    for(int i=0;i<len;i++)
    {//先倒着输入到numc[]中
        if(isdigit(a[i]))numa[len-i]=a[i]-'0';//字符转为数字放到相应的数组里面
        else numa[len-i]=a[i]-'A'+10;//防止是16进制
        if(isdigit(b[i]))numb[len-i]=b[i]-'0';
        else numb[len-i]=b[i]-'A'+10;
    }
    for(;lenc<=len;lenc++)
    {
        numc[lenc]=numa[lenc]+numb[lenc]+tmp;//加上进的那一位数
        tmp=numc[lenc]/n;//按n进制%
        numc[lenc]%=n;//求得进的数
    }
    numc[lenc]=tmp;
    while(numc[lenc]==0)lenc--;
    for(int i=lenc;i>=1;i--)//再反着输入到ans这个字符串中直接加就好
        ans+=six[numc[i]];
    return ans;
}
int n;
int main()
{
    cin>>n>>m;
    for(int i=0;i<+30;i++)
    {
        if(cherk(m))
        {
            printf("STEP=%d",i);
            return 0;
        }
        else m=add(n,m);
    }
    printf("Impossible!\n");
    return 0;
}

三.数学问题模拟

数学问题模拟

四.尺取法（双指针法）

1.都说小镇的切糕贵 (尺取法,字符串)

都说小镇的切糕贵
“一刀建林流泪，两刀马云都得跪。”摆在你面前的一长条切糕，你想尝到切糕里面所有的果仁，什么核桃呀，杏仁呀，巴旦木呀…但因为切糕很贵，你要选取一段连续的切糕，使得你能吃到这份切糕里所有的果仁，切记切糕贵，所以要选取最短的长度并且要包含所有的果仁，这里的果仁可以简单的看做a果仁，b果仁，c果仁….，输出能包含所有果仁的最短长度。换句话说出现的果仁都要出现在你所选的区间里面，输出这个区间的最短长度。
输入描述:
第一行包含整数n(1≤n≤100 000)——切糕的长度。第二行包含长度为n的字符串，它由英文字母表中的大写字母和小写字母组成。
输出描述:
输出一个整数，表示最小选取的长度。
示例1
输入

1
A

输出

1

示例2
输入

4
qqqE

输出

2

示例3
输入

9
bcdddbddc

输出

3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+10;
string s;
ll n,m,r,l,ans=1e9,sum,vis[maxn];
int main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)
    {
        if(!vis[s[i]])
            sum++,vis[s[i]]=1;
    }
    memset(vis,0,sizeof(vis));
    int now=0;
    while(r<n)//初始时l和r均为0从左往右走一遍取所有答案里的最小值即可
    {
        int k=s[r];
        if(!vis[k])now++;
        vis[k]++;
        r++;
        while(now==sum)
        {
            ll tmp=s[l];
            ans=min(ans,r-l);
            vis[tmp]--;
            if(!vis[tmp])now--;
            l++;
        }
    }
    cout<<ans<<endl;
}

umi和弓道

umi和弓道


首先确定umi所在位置的象限。很明显同一象限的点是不可能用挡板挡掉的，对于剩下的点找出线段和 xxx 轴或 yyy 轴的交点，统计坐标位置（如果存在交点的话）。之后双指针维护 xxx 轴上或者 yyy 轴挡住 n−kn-kn−k 个点的挡板长度最小值。注意 xxx 轴和 yyy 轴要分开计算。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+7;
const ll mod=1e9+7;
vector<double>v1,v2;
ll n,k;
int main()
{
    double x0,y0;
    cin>>x0>>y0>>n>>k;
    k=n-k;//把k换成至少要挡住几个靶子
    for(int i=0;i<n;++i)
    {
        double x,y;
        cin>>x>>y;
        if(x*x0<0)
            v2.push_back(y0-x0*(y-y0)/(x-x0));//y=kx+b(0,b)
        if(y*y0<0)
            v1.push_back(x0-y0*(x-x0)/(y-y0));//(b,0)
    }
    double meter=1e18;
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    if(v1.size()>=k)//说明放到x轴可以满足至少挡掉k个靶子的条件
    {
        double head=0,tail=k-1;
        while(tail<v1.size())
        {
            meter=min(meter,v1[tail]-v1[head]);
            tail++;head++;
        }
    }
    if(v2.size()>=k)
    {
        double head=0,tail=k-1;
        while(tail<v2.size())
        {
            meter=min(meter,v2[tail]-v2[head]);
            tail++;head++;
        }
    }
    if(meter==1e18)cout<<-1<<endl;
    else printf("%.7lf\n",meter);
    return 0;
}

五.奇怪的模拟

题目描述
给定一个序列，每次操作可以把某个数+1-1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

输入格式
第一行输入一个n，表示有 n ( n ≤ 5 ∗ 1 0 5 ) n(n \leq 5*10^5) n(n≤5∗105) 个数字。第二行输入n个整数，整数的绝对值不超过109

输出格式
输出一个数，表示最少的操作次数
思路：其实就是维护这个序列的单调性（单增）。遍历一遍，如果新加进来的数比当前最大的那个小，就把最大的变成新加进来的数，ans加上需要的操作数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+7;
const ll mod=1e9+7;
priority_queue<ll>q;
ll ans,n,m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--)
    {
        cin>>m;
        q.push(m);
        if(m<q.top())
        {
            ans+=q.top()-m;
            q.pop();
            q.push(m);
        }
    }
    cout<<ans<<endl;
    return 0;
}

x的位数=log10(x)+1;【取整】