2013 成都邀请赛
今年又要打邀请赛了，前段时间做比赛都被虐的够呛。感觉不会再爱了。。。所以挂了下去年的成都邀请赛的题目。发现简单题还是能切上几道的，可是难题就无能为力了。。
。阿门，还是水平差得远啊。。
。
（ps:近期感觉状态不佳。依靠了队友神勇的发挥。
。。
| Current Time: | 2014-05-15 08:43:24 | Contest Type: | Public |
| Start Time: | 2014-05-14 15:10:00 | Contest Status: | Ended |
| End Time: | 2014-05-14 20:10:00 | Manager: | ok_again |
| ID | Origin | Title | ||
|---|---|---|---|---|
| 2 / 2 | Problem A | HDU 4716 | A Computer Graphics Problem | |
| 1 / 1 | Problem B | HDU 4717 | The Moving Points | |
| Problem C | HDU 4718 | The LCIS on the Tree | ||
| 0 / 1 | Problem D | HDU 4719 | Oh My Holy FFF | |
| 1 / 1 | Problem E | HDU 4720 | Naive and Silly Muggles | |
| Problem F | HDU 4721 | Food and Productivity | ||
| 1 / 5 | Problem G | HDU 4722 | Good Numbers | |
| 1 / 1 | Problem H | HDU 4723 | How Long Do You Have to Draw | |
| Problem I | HDU 4724 | If You Know This,You Must Have NO GF | ||
| 1 / 4 | Problem J | HDU 4725 | The Shortest Path in Nya Graph | |
| 2 / 5 | Problem K | HDU 4726 | Kia's Calculation | |
| 1 / 2 | Problem L | HDU 4727 | The Number Off of FFF |
A，一如既往的最签到的题目。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 22000
#define INF 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
int main(){
int i,j,k,a,b;
int _,cas=1;
cin>>_;
while(_--){
cin>>a;
a/=10;
printf("Case #%d:
",cas++);
puts("*------------*");
b=a;
a=10-a;
while(a--){
puts("|............|");
}
while(b--){
puts("|------------|");
}
puts("*------------*");
}
return 0;
}
B题找的是最长的距离最短。是一个下凹的图形，直接三分就可以。
。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
struct point{
double x,y;
point(double a=0,double b=0){
x=a,y=b;
}
point operator+(const point &a){
return point(a.x+x,a.y+y);
}
point operator*(const double &a){
return point(x*a,y*a);
}
void input(){
scanf("%lf%lf",&x,&y);
}
}p[500],vp[500],tmp[500];
int n;
double dist(point a,point b){
double x=a.x-b.x;
double y=a.y-b.y;
return sqrt(x*x+y*y);
}
double calc(double t){
for(int i=0;i<n;i++) tmp[i]=p[i]+vp[i]*t;
double res=-1;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++) res=max(res,dist(tmp[i],tmp[j]));
}
return res;
}
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%d",&n);
for(int i=0;i<n;i++){
p[i].input(),vp[i].input();
}
double l=0,r=1e20,mid,midmid;
double ans=0;
while(l+eps<r){
mid=(l+r)/2;
midmid=(mid+r)/2;
double mid_=calc(mid);
double midmid_=calc(midmid);
if(mid_<midmid_){
r=midmid;ans=mid_;
}
else l=mid;
}
printf("Case #%d: ",cas);
printf("%.2f %.2f
",l,ans);
}
}
C题好像能够用LCA。保存6个值。各自是该区间的最长连续上升序列长度，左右端点连续上升序列长度，和分别得下降序列长度，便于查询时衔接用。
。。
比赛的时候想到了，可是没敲。。
。所以这题代码就不给了。
。。
D题好题线段树+dp+单调性。比赛的时候剩余时间不多了，没怎么想到正解。
。。后来看了下大家用的是线段树。自己想了想。的确能够用线段树维护。。。
当时就哭了。线段树中维护的是长度为L的那一段中，高度区间中dp[i]-h[i]的值(保存这个是由于。那个递推式。应该非常明显能看出来)。然后就是怎么往树中加点和删点了，明显，同一高度的假设后面出现的val值比掐面出现的val值还要大的话。前面哪一个肯定是无用的，所以我们须要维护每一个高度整体单调递减，然后删除的时候推断一下当前删除点是否在树中就能够了。
。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-7
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
const int maxn = 222222;
LL MAX[maxn<<2];
int fir[maxn], nxt[maxn], h[maxn], pre[maxn], last[maxn];
void PushUP(int rt)
{
MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void update(int p,LL sc,int l,int r,int rt)
{
if (l == r)
{
MAX[rt] = sc;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(p , sc , lson);
else update(p , sc , rson);
PushUP(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R)
{
return MAX[rt];
}
int m = (l + r) >> 1;
LL ret = -5;
if (L <= m) ret = max(ret , query(L , R , lson));
if (R > m) ret = max(ret , query(L , R , rson));
return ret;
}
LL dp[maxn];
void work(int cas)
{
int n, l;
scanf("%d%d", &n, &l);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &h[i]);
}
CLR(MAX, -1);CLR(dp, -1);
CLR(pre, -1);
printf("Case #%d: ", cas);
for(int i = 1; i <= n; i ++)
{
LL tmp;
if(h[i] == 1) tmp = -1;
else tmp = query(1, h[i] - 1, 1, 100000, 1);
if(tmp == -1 && i > l)
{
goto ed;
}
if(tmp == -1) tmp = 0;
tmp += 1ll*h[i]*h[i] - h[i];
dp[i] = tmp;
int j;
for(j = pre[h[i]]; j != -1; j = last[j])
{
if(dp[j] > dp[i]) break;
}
if(j == -1)
{
pre[h[i]] = i;
fir[h[i]] = i;
last[i] = -1;
update(h[i], dp[i], 1, 100000, 1);
}
else
{
pre[h[i]] = i;
nxt[j] = i;
last[i] = j;
}
if(i <= l) continue;
ed:;
if(fir[h[i - l]] == i - l)
{
if(pre[h[i - l]] == fir[h[i - l]])
{
pre[h[i - l]] = -1;
update(h[i - l], -1, 1, 100000, 1);
}
else
{
fir[h[i - l]] = nxt[fir[h[i - l]]];
update(h[i - l], dp[fir[h[i - l]]], 1, 100000, 1);
}
}
}
if(dp[n] == -1) puts("No solution");
else printf("%I64d
", dp[n] + h[n]);
}
int main()
{
int T, cas = 1;
scanf("%d", &T);
while(T --)
{
work(cas ++);
}
}
/*
555
5 1
24 5452 3542 452 14
*/
E题，这道题队友兴冲冲的就上去敲了。表示全然不知道题目。。。只是还是把代码附上吧。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
const double eps=1e-8;
struct point{
double x,y;
point(double a=0,double b=0){
x=a,y=b;
}
void input(){
scanf("%lf%lf",&x,&y);
}
}p[4],now,ori;
double r;
double dist(point a,point b){
double x=a.x-b.x;
double y=a.y-b.y;
return sqrt(x*x+y*y);
}
point getpoint(point a,point b,point c){
double bx=b.x-a.x,by=b.y-a.y;
double cx=c.x-a.x,cy=c.y-a.y;
double d=2*(bx*cy-by*cx);
double x=(cy*(bx*bx+by*by)-by*(cx*cx+cy*cy))/d+a.x;
double y=(bx*(cx*cx+cy*cy)-cx*(bx*bx+by*by))/d+a.y;
return point(x,y);
}
void MiniOver(){
ori=p[0];r=0;
for(int i=1;i<3;i++){
if(dist(ori,p[i])+eps>r){
ori=p[i],r=0;
for(int j=0;j<i;j++)
if(dist(ori,p[j])+eps>r){
ori.x=(p[i].x+p[j].x)/2;
ori.y=(p[i].y+p[j].y)/2;
r=dist(ori,p[j]);
for(int k=0;k<j;k++)
if(dist(ori,p[k])+eps>r){
ori=getpoint(p[i],p[j],p[k]);
r=dist(ori,p[k]);
}
}
}
}
}
int main(){
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++){
for(int j=0;j<3;j++) p[j].input();
MiniOver();
now.input();
printf("Case #%d: ",i);
if(dist(now,ori)<=r) puts("Danger");
else puts("Safe");
}
}
G题是一道简单的数位dp。
忘了0的情况。
。。
检查了n久。罪过啊。dp[i][j]表示长度为i位。余数为j有多少种数(包含前导零)。然后就显然了。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-7
#define PI acos(-1.0)
#define maxn 300
#define INF 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
LL dp[20][15];
void init()
{
CLR(dp, 0);
dp[0][0] = 1;
for(int i = 1; i < 20; i ++)
{
for(int j = 0; j < 10; j ++)
{
for(int k = 0; k < 10; k ++)
{
dp[i][(j + k) % 10] += dp[i - 1][j];
}
}
}
}
int c[25];
LL cal(LL a)
{
int len = 0;
while(a)
{
c[len ++] = a % 10;
a /= 10;
}
LL ret = 0;
int sum = 0;
for(int i = len - 1; i >= 0; i --)
{
if(i) for(int j = 1; j < 10; j ++)
{
ret += dp[i - 1][(10 - j)%10];
}
for(int j = 0; j < c[i]; j ++)
{
if(i == len - 1 && j == 0)
{
sum = (sum + 1) % 10;
continue;
}
ret += dp[i][(10 - sum) % 10];
sum = (sum + 1) % 10;
}
}
return ret;
}
int main()
{
int T, cas = 1;
init();
scanf("%d", &T);
while(T --)
{
LL a, b;
scanf("%I64d%I64d", &a, &b);
printf("Case #%d: ", cas ++);
LL ans = cal(b + 1) - cal(a);
if(a == 0) ans ++;
printf("%I64d
", ans);
}
}
H题，贪心一下就好了。最左边上下两点可定要连线，然后分别捡短的线连就能够了。。。
(正确性不可证。画了下图感觉挺对的。
。)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-7
#define PI acos(-1.0)
#define maxn 100100
#define inf 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
int c[maxn], d[maxn], ca;
double len(int i, int j)
{
return sqrt(1.0*ca*ca + 1.0*(c[i] - d[j])*(c[i] - d[j]));
}
int main()
{
int T, cas = 1;
int n, m, a, b;
scanf("%d", &T);
while(T --)
{
scanf("%d%d", &a, &b);
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++)
{
scanf("%d", &c[i]);
}
for(int i = 0; i < m; i ++)
{
scanf("%d", &d[i]);
}
int y1, y2; ca = abs(a - b); double ans = 0.0;
ans += len(0, 0);
for(y1 = 0, y2 = 0; y1 < n && y2 < m;)
{
double tmp1 = 1e20, tmp2 = 1e20;
if(y1 == n - 1 && y2 == m - 1) break;
if(y1 < n - 1) tmp1 = len(y1+1, y2);
if(y2 < m - 1) tmp2 = len(y1, y2+1);
if(tmp1 < tmp2) ans += tmp1, y1 ++;
else ans += tmp2, y2 ++;
}
printf("Case #%d: %.2f
", cas ++, ans);
}
}
J题想了n久才想到正解。。。本来想敲spfa的，队友说他先前敲的dij还在。就让他上去改了。
。。
大概就是我们须要把每一层都都当做一个节点。这种话第i层的点是能够更新第i+1层的全部点的，我们仅仅需把代表第i+1层的点更新了就能够了。。层节点代表的整层的信息。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-7
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
#define maxn 201000
#define maxe 601000
struct Edge{
int from,to,dis,next;
}edge[maxe];
int head[maxn];
int n,m,c,cnt;
void add(int q,int h,int len){
edge[cnt].from=q;
edge[cnt].to=h;
edge[cnt].dis=len;
edge[cnt].next=head[q];
head[q]=cnt;
cnt++;
}
void init(){
cnt=0;
memset(head,-1,sizeof head);
}
int belong[maxn];
vector<int>v[maxn];
struct node{
int u,c;
node(int u,int c):u(u),c(c){};
node(){};
friend bool operator <(node a,node b){
return a.c>b.c;
}
}tmp;
int can[maxn];
int dis[maxn];
bool used[maxn];
priority_queue<node>q;
void dij(int s,int ttt){
int t,u,w;
while(!q.empty())q.pop();
memset(used,0,sizeof used);
memset(dis,inf,sizeof dis);
tmp=node(s,0);
dis[s]=0;
q.push(tmp);
if(belong[s]+1<=2*n && can[belong[s]+1]){
tmp=node(belong[s]+1,c);
dis[belong[s]+1]=c;
q.push(tmp);
}
if(belong[s]-1>n && can[belong[s]-1]){
tmp=node(belong[s]-1,c);
dis[belong[s]-1]=c;
q.push(tmp);
}
while(!q.empty()){
tmp=q.top();
q.pop();
t=tmp.u;
if(used[t])continue;
else used[t]=true;
for(int i=head[t];i!=-1;i=edge[i].next){
u=edge[i].to;
w=edge[i].dis;
if(used[u])continue;
if(dis[t]+w<dis[u]){
dis[u]=dis[t]+w;
q.push(node(u,dis[u]));
if(u<=n){
if(belong[u]<=n*2 && can[belong[u]+1] && dis[t]+w+c < dis[ belong[u]+1 ]){
dis[ belong[u]+1 ]=dis[t]+w+c;
q.push(node(belong[u]+1,dis[t]+w+c));
}
if(belong[u]-1>n && can[belong[u]-1] && dis[t]+w+c < dis[ belong[u]-1 ]){
dis[ belong[u]-1 ]=dis[t]+w+c;
q.push(node(belong[u]-1,dis[t]+w+c));
}
}
}
}
if(t>n){
if(t<=n*2 && can[t+1] && dis[t]+c < dis[ t+1 ]){
dis[ t+1 ]=dis[t]+c;
q.push(node(t+1,dis[t]+c));
}
if(t-1>n && can[t-1] && dis[t]+c < dis[ t-1 ]){
dis[ t-1 ]=dis[t]+c;
q.push(node(t-1,dis[t]+c));
}
}
}
}
inline int get_int(){
int ret=0;
char c;
while(!isdigit(c=getchar()));
do{
ret =(ret<<3)+(ret<<1)+c-'0';
}while(isdigit(c=getchar()));
return ret;
}
int main(){
int _,cas=1,q,h,cost;
cin>>_;
while(_--){
n=get_int(),m=get_int(),c=get_int();
init();
memset(can,0,sizeof can);
for(int i=1;i<=n;i++){
belong[i]=get_int();
belong[i]+=n;
can[belong[i]]=1;
}
for(int i=0;i<m;i++){
q=get_int(),h=get_int(),cost=get_int();
add(belong[q],h,cost);
add(belong[h],q,cost);
add(q,h,cost);
add(h,q,cost);
}
dij(1,n);
printf("Case #%d: ",cas++);
int ans=min(dis[belong[n]],dis[n]);
if(ans==inf){
puts("-1");
}else{
printf("%d
",ans);
}
}
return 0;
}
K题是一道计数题？没看题。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 2200000
#define INF 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
char s[maxn];
int c1[11];
int cp1[11];
int cp2[11];
int c2[11];
int x1,x2;
int cnt[11];
int ctt[11];
int gethead(){
for(int i=9;i>=0;i--){
for(int j=0;j<=9;j++){
int tt = (i-j);
if(tt<0)tt+=10;
if(j==0||tt==0)continue;
if(c1[j]&&c2[tt]){
return i;
}
}
}
}
void getnext(){
for(int sum=9;sum>=0;sum--){
for(int a=0;a<=9;a++){
int b = (sum-a);
if(b<0)b+=10;
int cc = min(c1[a],c2[b]);
c1[a]-=cc;
c2[b]-=cc;
cnt[sum]+=cc;
}
}
bool ok;
for(int i=9;i>=0;i--){
if(cnt[i]==ctt[i])continue;
if(cnt[i]<ctt[i])ok=false;
else ok=true;
break;
}
if(ok){
for(int i=0;i<=9;i++){
ctt[i]=cnt[i];
}
}
}
int main(){
int _,cas=1;
cin>>_;
while(_--){
memset(c1,0,sizeof c1);
memset(c2,0,sizeof c2);
memset(cnt,0,sizeof cnt);
memset(ctt,0,sizeof ctt);
scanf("%s",s);
for(int i=0;s[i];i++)c1[s[i]-'0']++;
scanf("%s",s);
for(int i=0;s[i];i++)c2[s[i]-'0']++;
int h = gethead();
for(int i=0;i<=9;i++){
cp1[i]=c1[i];
cp2[i]=c2[i];
}
for(int i=0;i<=9;i++){
for(int j=0;j<=9;j++){
c1[j]=cp1[j];
c2[j]=cp2[j];
}
int tt = (h-i);
if(tt<0)tt+=10;
if(i==0||tt==0)continue;
if(c1[i]&&c2[tt]){
c1[i]--;
c2[tt]--;
memset(cnt,0,sizeof cnt);
getnext();
}
}
bool ok=false;
if(h!=0)ok=true;
printf("Case #%d: ",cas++);
if(h!=0)printf("%d",h);
for(int i=9;i>=1;i--){
while(ctt[i]--){
printf("%d",i);
ok=true;
}
}
if(ok){
while(ctt[0]--){
printf("%d",0);
}
}else{
printf("0");
}
puts("");
}
return 0;
}
L题，第二签到题。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define eps 1e-8
#define PI acos(-1.0)
#define maxn 220000
#define INF 0x3f3f3f3f
#define E exp(double(1))
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif
int s[maxn];
int main(){
int i,j,k,n,b;
int _,cas=1;
cin>>_;
while(_--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
b=-1;
for(int i=2;i<=n;i++){
if(s[i]-s[i-1]!=1){
b=i;
}
if(~b)break;
}
if(b==-1)b=1;
printf("Case #%d: %d
",cas++,b);
}
return 0;
}