A - Mike and Cellphone
问有没有多解，每个点按照给出的序列用向量法跑一遍
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N=2e5+;
const int INF=0x3f3f3f3f;
char s[];
int a[],n;
int mp[][]={-,-,-,-,
-,,,,
-,,,,
-,,,,
-,-,,-
};
typedef pair<int,int> pii;
pii pos[];
bool judge(int num){
int x=pos[num].first,y=pos[num].second;
for(int i=;i<=n;++i){
int px=pos[a[i]].first-pos[a[i-]].first;
int py=pos[a[i]].second-pos[a[i-]].second;
x+=px;y+=py;
if(x<||x>||y<||y>)return false;
if(mp[x][y]==-)return false;
}
return true;
}
int main(){
scanf("%d%s",&n,s+);
if(n==){printf("NO\n");return ;}
for(int i=;i<=n;++i)
a[i]=s[i]-'';
for(int i=;i<=;++i){
for(int j=;j<=;++j){
if(mp[i][j]==-)continue;
pos[mp[i][j]].first=i;
pos[mp[i][j]].second=j;
}
}
bool flag=false;
for(int i=;i<=;++i)
if(i!=a[]&&judge(i)){flag=true;break;}
if(flag)printf("NO\n");
else printf("YES\n");
return ;
}
B - Mike and Shortcuts
可能有更优的办法，一看数据，dij最短路水过
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N=2e5+;
const int INF=0x3f3f3f3f;
struct Edge{
int v,next;
LL w;
Edge(int a=,LL b=){v=a,w=b;}
bool operator<(const Edge &e)const{
return w>e.w;
}
}edge[N*];
int head[N],tot,n;
LL d[N];
void add(int u,int v,int w){
edge[tot].v=v;
edge[tot].w=w;
edge[tot].next=head[u];
head[u]=tot++;
}
priority_queue<Edge>q;
bool vis[N];
void dij(int s){
for(int i=;i<=n;++i)d[i]=INF,vis[i]=;
d[s]=,q.push(Edge(s,));
while(!q.empty()){
int u=q.top().v;
q.pop();
if(vis[u])continue;
vis[u]=;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(!vis[v]&&d[v]>d[u]+edge[i].w){
d[v]=d[u]+edge[i].w;
q.push(Edge(v,d[v]));
}
}
}
}
int main(){
scanf("%d",&n);
memset(head,-,sizeof(head));
for(int i=;i<=n;++i){
int x;scanf("%d",&x);
add(i,x,);
}
for(int i=;i<n;++i){
add(i,i+,);
add(i+,i,);
}
dij();
for(int i=;i<n;++i)printf("%I64d ",d[i]);
printf("%I64d\n",d[n]);
return ;
}
C - Mike and Chocolate Thieves
直接二分找就行，注意二分的移动
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N=2e5+;
const int INF=0x3f3f3f3f;
LL judge(LL mid){
LL sum=;
for(LL i=;i<=;++i){
sum+=mid/(i*i*i);
}
return sum;
}
int main(){
LL m;
scanf("%I64d",&m);
LL l=,r=1ll*1e18,ret=-;
while(l<=r){
LL mid=(l+r)>>;
LL tmp=judge(mid);
if(tmp>m)r=mid-;
else if(tmp==m)ret=mid,r=mid-;
else l=mid+;
}
printf("%I64d\n",ret);
return ;
}
D - Friends and Subsequences
这个题，不知道是我线段树写残了，还是线段树常数大，死活超时，RMQ才过，哪天去学一发ZKW线段树的姿势吧
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std;
#define For(i,j,n) for(int i=j;i<=n;i++)
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=2e5+;
const int maxn=;
const double eps=1e-; int a[N],b[N],MX[N][],MN[N][],n;
struct Tree
{
int l,r;
int mmax,mmin;
}tr[*N]; void build(int o,int L,int R)
{
for(int i=;i<=n;i++)
MX[i][]=a[i],MN[i][]=b[i];
for(int j=;(<<j)<=n;j++)
{
for(int i=;i+(<<j)-<=n;i++)
{
MX[i][j]=max(MX[i][j-],MX[i+(<<(j-))][j-]);
MN[i][j]=min(MN[i][j-],MN[i+(<<(j-))][j-]);
}
}
}
int query(int o,int L,int R,int flag)
{
if(flag)
{
int k = ;
while( (<<(k+)) <= R-L+) k ++ ;
return max(MX[L][k],MX[R-(<<k)+][k]);
}
else
{
int k = ;
while( (<<(k+)) <= R-L+) k ++ ;
return min(MN[L][k],MN[R-(<<k)+][k]);
}
}
int judge(int x,int y)
{
int mx=query(,x,y,),mn=query(,x,y,);
if(mx==mn)return ;
else if(mx>mn)return ;
return ; }
int main()
{
read(n);
For(i,,n)read(a[i]);
For(i,,n)read(b[i]);
build(,,n);
LL ret=;
for(int i=;i<=n;++i){
int ans1=-,ans2=-;
int l=i,r=n;
while(l<=r){
int m=l+r>>;
int t=judge(i,m);
if(t==)ans1=m,r=m-;
else if(t==)r=m-;
else l=m+;
}
l=i,r=n;
while(l<=r){
int m=l+r>>;
int t=judge(i,m);
if(t==)ans2=m,l=m+;
else if(t==)r=m-;
else l=m+;
}
if(ans1!=-&&ans2!=-)ret+=ans2-ans1+;
}
printf("%I64d\n",ret);
return ;
}
E - Mike and Geometry Problem
区间题，转化一下，看每个点被多少个线段覆盖（离散化搞搞），相同覆盖数统计，然后用组合数就行
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=2e5+;
const LL mod=1e9+;
struct Segment{
int l,r;
}p[N];
int pos[N*],n,k,tot,a[N*],b[*N];
LL dp[N],fac[N],inv[N];
LL quick_pow(LL a,LL num){
LL ret=;
while(num){
if(num&)ret=(ret*a)%mod;
num>>=;
a=(a*a)%mod;
}
return ret;
}
LL C(LL n,LL m){
return (fac[n]*inv[n-m])%mod*inv[m]%mod;
}
int main()
{
scanf("%d%d",&n,&k);
inv[]=fac[]=;
for(int i=;i<=n;++i){
fac[i]=1ll*i*fac[i-]%mod;
inv[i]=quick_pow(fac[i],mod-);
}
for(int i=;i<=n;++i){
scanf("%d%d",&p[i].l,&p[i].r);
pos[++tot]=p[i].l;
pos[++tot]=p[i].r;
}
sort(pos+,pos++tot);
tot=unique(pos+,pos++tot)-pos-;
for(int i=;i<=n;++i){
p[i].l=lower_bound(pos+,pos++tot,p[i].l)-pos;
p[i].r=lower_bound(pos+,pos++tot,p[i].r)-pos;
++a[p[i].l],--b[p[i].r];
}
for(int i=;i<=tot;++i){
a[i]+=a[i-];
++dp[a[i]];
if(i!=)dp[a[i-]]+=max(,pos[i]-pos[i-]-);
a[i]+=b[i];
}
LL ret=;
for(int i=k;i<=n;++i){
ret=(ret+dp[i]*C(i,k)%mod)%mod;
}
printf("%I64d\n",ret);
return ;
}