T1U3348 A2-回文数
https://www.luogu.org/problem/show?pid=U3348
考场上钻了牛角尖了，然后0分
#include<cstdio> #include<cmath> using namespace std; typedef long long LL; LL cnt[101]; int ans[101]; int main() { LL n; scanf("%lld",&n); LL now=9; int len; for(len=1;;len++) { if(n>now) n-=now; else break; if(len%2==0) now*=10; } int i=len+1>>1; n--; LL tmp=1; for(int j=1;j<i;j++) tmp*=10; for(int j=1;j<i;j++) { for(int k=(j==1);k<=9;k++) { if(j==1 && k==1) ans[j]=1; if(n>=tmp) ans[j]++,n-=tmp; else break; } tmp/=10; } for(int j=1;j<i;j++) printf("%d",ans[j]); printf("%d",n); if(len%2==0) printf("%d",n); for(int j=i-1;j;j--) printf("%d",ans[j]); }
T2[USACO08OPEN]农场危机Crisis on the Farm
https://www.luogu.org/problem/show?pid=2905
dp[k][i][j] 一共移动k次，其中东西方向i次，南北方向j次
东西：起始位置加减i
南北：起始位置加减j
最后倒退方案即可
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define N 1001 using namespace std; int sx[N],sy[N],bx[N],by[N]; int f[31][63][63],cnt[63][63]; char s[31][63][63]; int dx[4]={1,0,0,-1}; int dy[4]={0,1,-1,0}; char c[4]={'E','N','S','W'}; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d%d",&sx[i],&sy[i]); for(int i=1;i<=m;i++) scanf("%d%d",&bx[i],&by[i]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(abs(bx[j]-sx[i])+abs(by[j]-sy[i])<=k) cnt[bx[j]-sx[i]+k][by[j]-sy[i]+k]++; memset(f,-63,sizeof(f)); f[0][k][k]=0; for(int h=1;h<=k;h++) for(int i=0;i<=2*k;i++) for(int j=0;j<=2*k;j++) if(abs(i-k)+abs(j-k)<=h) f[h][i][j]=cnt[i][j]+max(max(f[h-1][i-1][j],f[h-1][i+1][j]),max(f[h-1][i][j-1],f[h-1][i][j+1])); int ans=-1; for(int i=0;i<=2*k;i++) for(int j=0;j<=2*k;j++) ans=max(ans,f[k][i][j]); for(int i=0;i<=2*k;i++) for(int j=0;j<=2*k;j++) if(f[k][i][j]==ans) s[k][i][j]='Z'; for(int h=k-1;h>=0;h--) for(int i=0;i<=2*k;i++) for(int j=0;j<=2*k;j++) if(abs(i-k)+abs(j-k)<=h) for(int l=0;l<4;l++) if(s[h+1][i+dx[l]][j+dy[l]] && f[h][i][j]+cnt[i+dx[l]][j+dy[l]]==f[h+1][i+dx[l]][j+dy[l]]) { s[h][i][j]=c[l]; break; } printf("%d ",ans); int x=k,y=k; for(int h=0;h<k;h++) { putchar(s[h][x][y]); for(int l=0;l<4;l++) if(s[h][x][y]==c[l]) { x+=dx[l]; y+=dy[l]; break; } } }
T3[USACO07DEC]观光奶牛Sightseeing Cows
https://daniu.luogu.org/problem/show?pid=2868
分数规划+spfa判环
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#define N 1001
#define M 5001
using namespace std;
int happy[N],cnt[N],n;
int front[N],to[M],nxt[M],val[M],tot;
double dis[N];
bool vis[N];
void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
}
bool spfa(double m)
{
for(int i=1;i<=n;i++) dis[i]=2e9;
memset(vis,false,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int>q;
vis[1]=true;
dis[1]=0;
q.push(1);
int now;
while(!q.empty())
{
now=q.front();
q.pop(); vis[now]=false;
for(int i=front[now];i;i=nxt[i])
if(dis[to[i]]>dis[now]+m*val[i]-happy[to[i]])
{
dis[to[i]]=dis[now]+m*val[i]-happy[to[i]];
if(!vis[to[i]])
{
vis[to[i]]=true;
q.push(to[i]);
cnt[to[i]]++;
if(cnt[to[i]]>n) return true;
}
}
}
return false;
}
int main()
{
int p;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++) scanf("%d",&happy[i]);
int u,v,w;
while(p--)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
double l,r=1000,mid;
while(fabs(l-r)>1e-3)
{
mid=(l+r)/2;
if(spfa(mid)) l=mid;
else r=mid;
}
printf("%.2lf",l);
}