问题 A: 东风谷早苗
时间限制: 1 Sec 内存限制: 128 MB
【问题描述】
在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(0,0)的位置，并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。
【输入】
第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令。
第2行：一个正整数T。
【输出】
第1行：两个整数，表示T秒时，钢达姆的坐标。
【输入输出样例】
robot.in
robot.out
NSWWNSNEEWN
12
-1 3
【数据范围】
对于60%的数据：T <= 500,000且命令串长度 <= 5,000；
对于100%的数据：T <= 2,000,000,000且命令串长度<= 5,000。
【注意】
向东移动，坐标改变改变为(X+1,Y);
向南移动，坐标改变改变为(X,Y-1);
向西移动，坐标改变改变为(X-1,Y);
向北移动，坐标改变改变为(X,Y+1)。
输入
输出
提示
模拟(ps:这种水题不多写点真的容易挂)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
string s;
int t;
int x,y;
main(){
cin>>s;
int len=s.size();
scanf("%lld",&t);
int now=0;
x=0;
y=0;
for(int now=0;now<len;now++){
if(s[now]=='N')y++;
if(s[now]=='S') y--;
if(s[now]=='E') x++;
if(s[now]=='W') x--;
}
x=(t/len)*x;
y=(t/len)*y;
int yu=t%len;
for(int i=1;i<=yu;i++){
if(s[now]=='N') y++;
if(s[now]=='S') y--;
if(s[now]=='E') x++;
if(s[now]=='W') x--;
now++;
}
cout<<x<<" "<<y;
return 0;
}
【问题描述】
小Y去Lhc Market购物，不过这个Market有个不成文的规定，就是买东西不找零。比如说，《算法导论》要68元，你付了100元，他会收下，但不会找你32元，于是你就用100元买了68元的东西，亏大了。小Y身边只有n张纸币，每张纸币有一个正整数面额p，Market里有k种商品，每种商品都有一个正整数单价t。小Y现在想知道，用他的纸币能恰好凑出哪些商品的价格。例如：5 1 4 8 9能凑出17=8+9, 6=1+5, 10=1+9等，但不能凑出2,3等。
【输入格式】
第1行：一个整数n(1 <= n <= 34),表示小Y有n张纸币。
第2至n+1行：每行一个正整数p(1 <= p <= 20000000)，表示每张纸币的面额。
第n+2行：一个整数k(1 <= k <= 10)，表示有k种商品。
第n+3至n+k+2行：每行一个正整数t(1 <= t <= 2000000000)，表示每种商品的价格。
【输出格式】
共k行，第i行输出第i种商品的钱是否能凑出。如果能，输出“possible”，否则输出“impossible”(引号不输出，区分大小写)。
【样例输入】
3
2
7
9
2
11
4
【样例输出】
possible
impossible
【约定】
20%的数据 n <= 20；
20%的数据 p <= 100。
输入
输出
提示
MEET IN THE MIDDLE
一会再改，先存代码
#pragma G++ optimize (2)
#pragma GCC optimize (2)
#include<bits/stdc++.h>
#define ll long long
#define mod 199721
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll d1[200050],a[50];
int tot1=0,n;
void dfs1(int step,ll sum)
{
if(step==n/2+1)
{
d1[++tot1]=sum;
return;
}
dfs1(step+1,sum);
dfs1(step+1,sum+a[step]);
}
map<ll,int>mp;
void dfs2(int step,ll sum)
{
if(step==n+1)
{
mp[sum]=1;
return;
}
dfs2(step+1,sum);
dfs2(step+1,sum+a[step]);
}
int main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
dfs1(1,0);
dfs2(n/2+1,0);
int k=read();
while(k--)
{
ll x=read();
bool flag=0;
for(int i=1;i<=tot1;i++)
if(mp.count(x-d1[i]))
{
puts("possible");
flag=1;
break;
}
if(!flag) puts("impossible");
}
}
T3
题目描述 Description
在幻想乡，藤原妹红是拥有不老不死能力的人类。虽然不喜欢与人们交流，妹红仍然保护着误入迷途竹林村民。由于算得上是幻想乡最强的人类，对于她而言，迷途竹林的单向道路亦可以逆行。在妹红眼中，迷途竹林可以视为一个由N个路口(编号1..N)，M条不同长度双向路连接的区域。妹红所在的红之自警队为了方便在迷途竹林中行动，绘制了一张特殊的迷途竹林地图，这张地图上只保留了N-1条道路，这些道路保证了任意两个路口间有且仅有一条路径，并且满足所有保留的道路长度之和最小，我们称这些道路为『自警队道路』。现在妹红打算在其中一个连接有多条『自警队道路』的路口设立根据地，当去掉根据地这个根据地所在路口后，就会出现某些路口间无法通过『自警队道路』相互连通的情况，我们认为这时仍然能够通过『自警队道路』连通的路口属于同一个『区域』。妹红希望最后每个『区域』的『自警队道路』总长尽可能平均，请计算出她应该选择哪一个路口作为根据地。
下例中红色的路口为妹红选择的根据地，实线边表示『自警队道路』，绿色虚线边表示非『自警队道路』，数字表示边权，『自警队道路』中相同颜色的实线边代表属于同一个『区域』：
(尽可能平均即权重最小，设每一块『区域』的路线总长为Length[i]，平均路线长度为Avg=SUM{Length[i]}/区域数，权重d=∑( (Length[i]-Avg)^2 ) )
输入描述 Input Description
第1行：2个正整数N,M
第2..M+1行：每行2个整数u,v和1个实数len，表示u,v之间存在长度为len的边
输出描述 Output Description
第1行：1个整数，最后选择的路口编号，存在多个可选路口时选择编号小的
样例输入 Sample Input
3 3
3 1 5
3 2 4
1 2 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
对于60%的数据：3 ≤ N ≤ 2,000，N-1 ≤ M ≤ 50,000
对于100%的数据：3 ≤ N ≤ 40,000，N-1 ≤ M ≤ 200,000
对于100%的数据：0 < len ≤ 100,000,000
提示
样例解释：
妹红的『自警队道路』为(1,2)和(2,3)。
只能选择2作为根据地，产生的两个区域Length[i]分别为3和4。
所以方差为：(4-3.5)^2 + (3-3.5)^2 = 0.5
注意：
保证不存在相同距离的线路，两个路口间可能出现多条路径，且任意点对间至少存在一条路径。
#include<bits/stdc++.h>
#define MAXN 50005
#define MAXE 400005
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Edge
{
int v,next;
double w;
}e[MAXN*2];
int head[MAXN],cnt=0;
inline void addedge(int u,int v,double w)
{
cnt++;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
struct line
{
int u,v;
double w;
bool operator<(const line &a)const{
return w<a.w;}
}l[MAXE];
int n,m;
int father[MAXN];
int finds(int x)
{
if(father[x]==x) return x;
return father[x]=finds(father[x]);
}
int size[MAXN],deg[MAXN],pos;
double val[MAXN],sum=0;
double ans=1e40;
void dfs(int x,int fa)
{
size[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
deg[x]++;
if(v==fa) continue;
dfs(v,x);
size[x]+=size[v];
val[x]+=val[v]+e[i].w;
}
if(deg[x]==1) return;
double avg=(double)(1.0*sum/deg[x]);
double tt=(double)(1.0*sum-val[x]);
double res=(tt-avg)*(tt-avg);
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
tt=(double)(1.0*val[v]+e[i].w);
res+=(tt-avg)*(tt-avg);
}
if(res<ans)
{
ans=res;
pos=x;
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
l[i].u=read(),l[i].v=read();
scanf("%lf",&l[i].w);
}
sort(l+1,l+m+1);
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++)
{
int u=finds(l[i].u),v=finds(l[i].v);
if(u!=v)
{
father[v]=u;
sum+=l[i].w;
addedge(l[i].u,l[i].v,l[i].w);
addedge(l[i].v,l[i].u,l[i].w);
}
}
dfs(1,0);
cout<<pos;
}
京公网安备 11010502036488号