（咕咕咕，咕了快一年的bu题。。
A.CCPC直播
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6297
题意：rt。
分析：模拟。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t; scanf("%d",&t);
while (t--){
int pro,num; string rank,name,now;
cin >> rank;
cin >> name;
cin >> pro;
cin >> now;
if (now=="Running") cin >> num;
for (int i=;i<-rank.size();i++) cout << " ";
cout << rank << "|";
cout << name;
for (int i=;i<-name.size();i++) cout << " ";
cout << "|";
cout << pro << "|[";
if (now=="Running"){
for (int i=;i<num;i++) cout << "X";
for (int i=;i<-num;i++) cout << " ";
}
else{
for (int i=;i<;i++) cout << " ";
if (now=="FB"){
cout << "AC*";
for (int i=;i<;i++) cout << " ";
}
else{
cout << now;
for (int i=;i<-now.size()-;i++) cout << " ";
}
}
cout << "]\n";
}
return ;
}
P6297
B.口算训练
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6287
题意：T（T<=10）组数据。给定n（n<=1e5）个数，a1,a2,....an（ai<=1e5）。m（m<=1e5）个询问，询问在区间[l,r[内所有数的乘积是否为k（k<=1e5）的倍数。
分析：（卡住了。。wsl
C.缺失的数据范围
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6288
题意：求解最大的正整数n，满足公式：。数据范围：1<=a,b<=10，1e6<=k<=1e18。
分析：要求取得尽可能大的n。所以可以二分答案一直找尽可能大的n。注意，在check函数内，使用库函数log会有精度损失，需要手写log并上取整。
另，1e18相乘会爆ll，需要先除再比较大小。（wa了n发的坑点。。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll _log(ll n){
ll ans=;
while (){
if (n==) return ans;
else if (n==) return ans+;
n-=n/;
ans++;
}
}
bool check(ll xx,int a,int b,ll k){
ll tmp=_log(xx);
ll num=;
while (a--){
if (num*tmp>k) return false;
num*=xx;
}
while (b--){
if (num*tmp>k) return false;
num*=tmp;
}
return true;
}
int main(){
int t; scanf("%d",&t);
int a,b; ll k,ans;
while (t--){
scanf("%d%d%I64d",&a,&b,&k);
ll l=,r=k,mid;
while (l<=r){
mid=(l+r)/;
if (check(mid,a,b,k)){
ans=mid; l=mid+;
}
else r=mid-;
}
printf("%I64d\n",ans);
}
return ;
}
P6288
D.
E.奢侈的旅行
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6290
题意：n个点，m条单向路，每条路的描述为（u，v，a，b）。初始等级为1，通过每条路的要求为：通过这条路的花费为cost=，那么只有满足：
时，才可以通过这条路。并且level提升a。问从1--n的最小花费。
分析：对于每一条边的通过限制条件，经过简单处理可以变成：。同时，对于每一次的花费相加（底数相同的log相加，真数相乘），化简之后可以变成：
。所以在跑最短路时可以直接用ll来做，避免因为double的精度所导致的错误。
dijk+堆优化。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const double inf=2e18;
struct edge{
int to;
ll a,b;
};
vector<edge> mp[maxn];
struct node{
int to; ll cost;
friend bool operator < (node p,node q){
return p.cost>q.cost;
}
};
int n,m;
bool vis[maxn]; ll dist[maxn];
void dijk(){
priority_queue<node> q;
for (int i=;i<=n;i++) vis[i]=false,dist[i]=inf;
q.push({,1.0});
dist[]=;
while (!q.empty()){
node tmp=q.top(); q.pop();
if (vis[tmp.to]) continue;
vis[tmp.to]=true;
for (int i=;i<mp[tmp.to].size();i++){
edge res=mp[tmp.to][i];
if (dist[res.to]>dist[tmp.to]+res.a && (dist[tmp.to]+res.a)/dist[tmp.to]>=(1ll<<res.b)){
dist[res.to]=dist[tmp.to]+res.a;
q.push({res.to,dist[res.to]});
}
}
}
}
int main(){
int t; scanf("%d",&t);
int u,v; ll a,b;
while (t--){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) mp[i].clear();
for (int i=;i<m;i++){
scanf("%d%d%lld%lld",&u,&v,&a,&b);
mp[u].push_back({v,a,b});
}
dijk();
if (dist[n]==inf){
printf("-1\n"); continue;
}
int num=;
while (dist[n]){
dist[n]/=;
++num;
}
printf("%d\n",num-);
}
return ;
}
P6290
F.对称数
传送：
题意：
分析：
G.赛题分析
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6292
题意：rt。
分析：模拟。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n,m,x; scanf("%d",&t);
int _=;
while (t--){
scanf("%d%d",&n,&m);
printf("Problem %d:\n",++_);
int ans=1e5;
for (int i=;i<n;i++){
scanf("%d",&x);
ans=min(ans,x);
}
printf("Shortest judge solution: %d bytes.\n",ans);
ans=1e5;
for (int i=;i<m;i++){
scanf("%d",&x);
ans=min(ans,x);
}
if (m!=) printf("Shortest team solution: %d bytes.\n",ans);
else printf("Shortest team solution: N/A bytes.\n");
}
return ;
}
P6292
H.
I.SA-IS后缀数组
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6294
题意：有一个长度为n的字符串，定义Si为以第i个字母开始的字符串后缀。求问，对于1<=i<n，Si与Si+1的字典序大小。
分析：思考一下。发现，只需要判断当前字符和下一个字符的大小关系即可，如果相同，就继续比较下一个位置。从后往前做即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+;
char s[maxn],ans[maxn];
int main(){
int t,n; scanf("%d",&t);
while (t--){
scanf("%d",&n);
scanf("%s",s);
ans[n-]='>';
for (int i=n-;i>=;i--){
if (s[i]>s[i+]) ans[i]='>';
else if (s[i]<s[i+]) ans[i]='<';
else ans[i]=ans[i+];
}
for (int i=;i<n-;i++) printf("%c",ans[i]);
printf("\n");
}
return ;
}
P6294
J.回文树
传送：http://acm.hdu.edu.cn/showproblem.php?pid=6295
题意：有n个结点的树，每个点有一个值a[i]，且a[i]的取值为1--n内随机的。求问，对于任意一对结点<u,v>，表示从u到v的树上的最短路径，路径上依此所经过的数字是回文串的点对数。
分析：因为ai取值随机。那么直接枚举回文串的中心即可（中心可以为点，也可以为一条边）。然后向两边不断扩展暴力即可。
同时注意题目中的限制条件，要求1<=u<=v<=n。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
vector<int> mp[maxn];
int a[maxn];
bool cmp(int p,int q){return a[p]<a[q] || a[p]==a[q] && p<q;}
ll ans;
void dfs(int x,int fx,int y,int fy){
if (a[x]!=a[y]) return ;
if (fx!= && x==y) return ;
if (x<=y) ans++;
int j=,k;
for (int i=;i<mp[x].size();i++){
if (mp[x][i]!=fx){
while (j<mp[y].size() && a[mp[y][j]]<a[mp[x][i]]) j++;
k=j;
while (k<mp[y].size() && a[mp[y][k]]<=a[mp[x][i]]) k++;
for (int t=j;t<k;t++)
if (mp[y][t]!=fy) dfs(mp[x][i],x,mp[y][t],y);
}
}
}
int main(){
int t,n,x,y; scanf("%d",&t);
while (t--){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i]),mp[i].clear();
ans=;
for (int i=;i<n-;i++){
scanf("%d%d",&x,&y);
mp[x].push_back(y);
mp[y].push_back(x);
}
for (int i=;i<=n;i++) sort(mp[i].begin(),mp[i].end(),cmp);
for (int i=;i<=n;i++) dfs(i,,i,); //点作为回文中心
for (int i=;i<=n;i++){
for (int j=;j<mp[i].size();j++){
dfs(i,mp[i][j],mp[i][j],i); //边作为回文中心
}
}
printf("%lld\n",ans);
}
return ;
}
P6295
K.