| by XianKa | No comments

## Q1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
int n, dirx[maxn], diry[maxn], desx, desy,inix,iniy;
string s;
int main()
{
cin >> inix >> iniy >> desx >> desy;
if(inix == desx && iniy == desy)
{cout<<0;return 0;}
cin >> n >> s;
for(int i = 1; i <= n; i++ )
{
if(s[i - 1] == 'U') diry[i] = 1;
if(s[i - 1] == 'D') 
| by XianKa | No comments

### 【斜率优化】cf311b Cats Transport

i j k 三层循环，把 i 看作不变量，对 j k 做斜率优化。同时由于每次只用到了i – 1的状态，所以可以把 … Read the rest

| by XianKa | No comments

### 【斜率优化】牛客练习赛40D 小A与最大子段和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+233;
ll a[maxn],b[maxn],f[maxn];
int q[maxn];
int l=1,r=1;
int n;
int brf(int k)
{
if(l == r) return q[l];
int L=l,R=r;
while(L<R)
{
int mid=(L+R)>>1;
if(b[q[mid + 1]] * q[mid + 1] - a[q[mid + 1]] - b[q[mid]] * q[mid] + a[q[mid]]
>= b[k] * (q[mid + 1] - q[mid])) L = mid + 1;
else R 
| by XianKa | No comments

### 蓝桥杯 算法提高 周期字串

#include<bits/stdc++.h>
using namespace std;
char a[111];
int nxt[111];
int n;
void kmp()
{
nxt[1]=0;
for(int i=2,j=0;i<=n;i++)
{
while(j>0 && a[i]!=a[j+1]) j=nxt[j];
if(a[i]==a[j+1]) j++;
nxt[i]=j;
}
}
int main()
{
scanf("%s",a+1);
n=strlen(a+1);
kmp();
if(n%(n-nxt[n])==0) printf("%d",n-nxt[n]);
else printf("%d",n);
}

| by XianKa | No comments

# 蓝桥杯历届试题做题记录

## 解题报告 与 题解

[TOC]

### PREV-55 小计算器

#### 题解

模拟

#### 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,char> eco;
map<char,ll> deco;
int k=10;
ll ans=0;
char num[99];
void init()
{
for(ll i=0;i<=9;i++)
{
eco[i]=i+'0';
deco[i+'0']=i;
}
for(ll i='A';i<='Z';i++)
{
eco[i-'A'+10]=i;
deco[i]=i-'A'+10;
}
}
ll getnum()
{
ll tmp=1;
ll ret=0;
for(int i=strlen(num)-1;i>=0;i--)
{
ret+=tmp*deco[num[i]];
tmp*=k;
}
return ret;
}
void pout(ll tnum)
{
//cout<<tnum<<endl;
if(tnum==0)
{
printf("0\n");
return;

| by XianKa | 2 comments

### 蓝桥杯历届试题 区间移位

http://lx.lanqiao.cn/problem.page?gpid=T451

wjjj随便猜了个结论就猜对了（%%%）。二分后按照b排序，优先选b小的。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-12;
const int N=20000;
vector<pii> ab;
int vis[10001];
multiset<pii> c2;
int line[10001];
int main()
{
int n,a,b;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
a*=2;b*=2;
c2.insert({b,a});
}
int l=0,r=N;
while(r>l)
{
multiset<pii> c1(c2);
int mid=(l+r)>>1;
int now=0;
while(1)
{
int flag=0;
multiset<pii>::iterator it;
for(it=c1.begin();it!=c1.end();it++)
{
pii tmp=*it;
int tta=tmp.second,ttb=tmp.first;
if(tta-mid <= now && ttb+mid >= now)
{
flag=1;
int len=ttb-tta;
if(now<=tta+mid) 
| by XianKa | No comments

### 【数论】CF1110C

http://codeforces.com/problemset/problem/1110/C

• 首先注意到a^b和a&b的每一位都是相反的，所以说很容易想到构造一个b使得b&a=0，这样答案就是a^b。构造方法就是把a的每一位1变成0，0变成1。
• 对于a的每一位全是1的情况需要单独讨论。
• 如果a的每一位都是1，任取一个b，可以得到a^b=a-b , a&b=b 这个结论。那么问题就变成了求gcd(a-b,b)，也就是gcd(a,b)_max。
• 对于求最大的gcd，把a分解质因数，除掉其中一个最小的质因子，就是答案。
• 由于本题时间不紧，而且cf测评机都是香港记者，所以可以直接根号复杂度暴力分解。当然也可以预处理质数表
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q,a;
int main()
{
scanf("%d",&q);
while(q--)
{
scanf("%d",&a);
//a=q;
int res=0;
for(int i=0;(1<<i)+res < a;i++)
{
if(!((1<<i)&a) )
res+=(1<<i);
//cout<<res<<'-';
}
if(res) printf("%d\n",res^a);
else
{
bool flag=true;
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
flag=false;
printf("%d\n",a/i);
break;
}
}
if(flag) printf("1\n");
}
}
}

| by XianKa | No comments

### 牛客19寒假R2I

https://ac.nowcoder.com/acm/contest/327/I

• 对于每个数分解质因子，sqrt(n)的复杂度，打素数表可以更快。2000*20=40000
• 对于每个数枚举其他数，由于分解的时候质因子是有序的，所以对两个数可以归并排序的方法线性合并质因子。
• 小知识点：对于1e9以内的数，一般不同的质因子个数不超过10个
• 所以对于合并的复杂度，不会超过o(20)，2000*2000*20=80000000
• 总复杂度小于1e8，且常数极小，可以接受
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,ans=0;
vector<pii> a[2002];
int main()
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
{
int k;
scanf("%d",&k);
for(int i=2;i*i<=k;i++)
{
int res=0;
if(k%i==0)
{
while(k%i==0)
{
k/=i;
res++;
}
a[j].push_back(make_pair(i,res));
}
}
if(k>1) a[j].push_back(make_pair(k,1));
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
int l=0,r=0,tmp=1;
auto &aa=a[i];
auto &bb=a[j];
while(l<aa.size() && r<bb.size())
{
if(aa[l].first<bb[r].first) tmp*=aa[l++].second+1;
else if(aa[l].first>bb[r].first) tmp*=bb[r++].second+1;
else tmp*=aa[l++].second+bb[r++].second+1;
}
while(l<aa.size()) tmp*=aa[l++].second+1;
while(r<bb.size()) tmp*=bb[r++].second+1;
if(tmp<=10) ans++;
}
}
printf("%d\n",ans);

| by XianKa | No comments

### 【数论】欧拉降幂，费马小定理求逆元，阶乘逆元

• 首先这题模数是一个大质数，所以考虑求分母的逆元
• 由于只需要算一次，没有变量也没有多次询问，所以直接暴力求20192019!%p的结果，然后用费马小定理求出其逆元即可
• 对于分母，也可以用欧拉定理来降幂，由于p是个质数，所以p的欧拉函数值就是p-1，可以直接放上分子，然后对分子进行快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll qsm(ll n,ll k,ll md)
{
ll res=1;
while(k)
{
if(k&1) res=(res*n)%md;
n=(n*n)%md;
k>>=1;
}
return res%md;
}
int main()
{
ll fac=1;
for(int i=1;i<=20192019;i++) fac=(fac*i)%mod;
ll inv=qsm(fac,mod-2,mod);
ll son=qsm(2019,qsm(2019,2019,mod-1),mod);
cout<<inv*son%mod<<endl;
}

• 补充：
• 对于阶乘的逆元，可以$O(N)$预处理出其逆元。
• 假设用费马小定理求出了$q!$的逆元$(q!)^{-1}$。那么就有
• $(q!) * (q!)^{-1} \equiv 1$
• $(q-1)! * q * (q!)^{-1} \equiv 1$
• 从上式可以看出$(q-1)!$的逆元就是$q * q!^{-1}$
• fact[0]=1;
for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
invfact[n]=qsm(n,mod-2);
for(int i=n;i>=1;i--) invfact[i-1]=invfact[i]*i%mod;

| by XianKa | No comments

### 【组合|卡特兰数】牛客19寒假R1H

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+233;
int primes[N], cnt;
ll st[N];
ll sum[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; j < cnt && i * primes[j] <= n; j ++ )
{
st[primes[j] * i] = primes[j];
if (i % primes[j]