A题（(Mike and Cellphone）
看起来好像需要模拟数字键位的运动,可是,
只要判断出那些必然YES的数字组合不就好了么
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int vis[];
inline bool judge()
{
if(vis[]&&vis[]) return true;
if(vis[]&&vis[]) return true;
if(vis[]&&(vis[]||vis[]||vis[])) return true;
if((vis[]||vis[])&&vis[]&&vis[]) return true;
if((vis[]||vis[])&&vis[]&&vis[]) return true;
if(vis[]&&vis[]&&vis[]) return true;
return false;
}
char ch[];
int main()
{
int n;
while(~scanf("%d",&n))
{
scanf("%s",ch);
int x;
memset(vis,,sizeof(vis));
for(int i=;i<n;i++)
{
x=ch[i]-'';
vis[x]=;
}
if(judge())
{
printf("YES\n");
}
else printf("NO\n");
}
return ;
}
B题（(Mike and Shortcuts）
题意:对于n个点,可以从1开始直接走过去,代价是abs(x-1),也可以通过某种捷径而到,代价是1
解题:难点在于建图,每个点之间都连通,难道要建n^2条边?
1.在不考虑捷径的情况下,每两个点之间的距离是两者之差的绝对值
2.任意两点没有必要都建一条边使得他们直接相连,对于任意的一个点,只要相邻的两个
点与它建一条代价为1的边,这样任意两点都能够间接相连,而且代价累加起来正好是距离。
3.最后再加上捷径,最多有n条,总共会有3*n条边,由于不存在负权回路,使用DIJKSTRA+优先队列
优化,时间复杂度是O(ElogE).
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int Max=+;
int abs(int x) {return x>=?x:-x;}
int n,m;
struct Edge{
int from,to,dist;
Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
vector <Edge> edges;
vector <int> G[Max];
int d[Max];
void Init()
{
for(int i=;i<=n;i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int dist)
{
edges.push_back(Edge(from,to,dist));
m=edges.size();
G[from].push_back(m-);
}
struct node
{
int d,u;
node(int dd,int uu):d(dd),u(uu){};
bool operator < (const node & rhs) const {
return d>rhs.d;
}
};
const int INF=0x3f3f3f3f;
bool done[Max];
void Dijkstra(int s)
{
priority_queue<node>Q;
for(int i=;i<=n;i++) d[i]=INF;
d[s]=;
memset(done,,sizeof(done));
Q.push(node(,s));
while(!Q.empty())
{
node x=Q.top();Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
for(int i=;i<G[u].size();i++)
{
Edge &e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist)
{
d[e.to]=d[u]+e.dist;
Q.push(node(d[e.to],e.to));
}
}
}
}
int main()
{
while(~scanf("%d",&n))
{
int x;
Init();
for(int i=;i<=n;i++)
{
scanf("%d",&x);
AddEdge(i-,i,);
AddEdge(i+,i,);
AddEdge(i,x,);
}
Dijkstra();
for(int i=;i<=n;i++)
{
if(i!=) printf(" ");
printf("%d",d[i]);
}
puts("");
}
return ;
}
C题（Mike and Chocolate Thieves）
要求一个四元组,并且这个四元组成k倍关系。
可知n越大,种数越多,且种类数取决于k。
对于这样一个有序关系,可以使用二分查找
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
LL cacu(LL x)
{
LL sum=;
for(LL i=;i<=1e6;i++)
{
if(i*i*i>x) break;
sum+=x/(i*i*i);
}
return sum;
}
int main()
{
while(~scanf("%I64d",&n))
{
LL l=,r=1e18,m;
while(l<=r)
{
m=(l+r)>>;
if(cacu(m)>=n) r=m-;
else l=m+;
}
if(cacu(r+)!=n) puts("-1");
else printf("%I64d\n",r+);
}
return ;
}
D题（Friends and Subsequences）
对于每个max(ai)==min(bj)
枚举所有的左区间,
max(ai)是递增的,min(bj)是递减的
因此对max(ai)-min(bj)可以进行二分查找
二分查找满足条件的下界和上界
RMQ可以使用ST算法实现
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+;
int A[N],B[N];
int mn[N][],mx[N][];
void RMQ_init(int n)
{
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 RMQ(int L,int R,int flag)
{
int k=;
while((<<(k+))<=R-L+) k++;
if(flag)
return max(mx[L][k],mx[R-(<<k)+][k]);
else
return min(mn[L][k],mn[R-(<<k)+][k]);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++) scanf("%d",&A[i]);
for(int i=;i<=n;i++) scanf("%d",&B[i]);
RMQ_init(n);
long long sum=;
for(int i=;i<=n;i++)
{
int l,r,mid,ansr,ansl,ma,mb;
ansl=ansr=-;
l=i;r=n;
while(l<=r)
{
mid=l+(r-l)/;
ma=RMQ(i,mid,);mb=RMQ(i,mid,);
if(ma==mb) l=mid+,ansr=mid;
else
if(ma>mb) r=mid-;
else l=mid+;
}
l=i;r=n;
while(l<=r)
{
mid=l+(r-l)/;
ma=RMQ(i,mid,);mb=RMQ(i,mid,);
if(ma==mb) r=mid-,ansl=mid;
else
if(ma>mb) r=mid-;
else l=mid+;
}
if(ansl==-||ansr==-) continue;
sum+=ansr-ansl+;
}
printf("%I64d\n",sum);
}
return ;
}
E题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+;
const int MOD=1e9+;
LL fact[N];
LL qpow(LL x,LL k)
{
LL base=x,ans=;
while(k)
{
if(k&) ans=(ans*base)%MOD;
base=(base*base)%MOD;
k>>=;
}
return ans;
}
LL inv(LL x)
{
return qpow(x,MOD-);
}
LL C(int n,int k)
{
LL ans=fact[n]*inv(fact[k])%MOD*inv(fact[n-k])%MOD;
return ans;
}
map<int,int>book;
int main()
{
int n,k,l,r,ans,add,dist;
cin>>n>>k;
fact[]=;
for(int i=;i<=n;i++) fact[i]=(fact[i-]*i)%MOD;
for(int i=;i<n;i++)
{
cin>>l>>r;
book[l]++;
book[r+]--;
}
ans=add=;
l=book.begin()->first;
map<int,int>::iterator it;
for(it=book.begin();it!=book.end();it++)
{
dist=it->first-l;
if(add>=k) ans=(ans+C(add,k)*dist)%MOD;
add+=it->second;
l=it->first;
}
cout<<ans<<endl;
return ;
}