| # | Name | ||
|---|---|---|---|
| A |
standard input/output
1 s, 256 MB |
|
|
| B |
standard input/output
2 s, 256 MB |
|
|
| C |
standard input/output
2 s, 256 MB |
|
|
| D |
standard input/output
1 s, 256 MB |
|
|
| E |
standard input/output
2 s, 256 MB |
|
A Summer Camp
题意：有个 "123456789101112131415..."这样规律的字符串，求其中第n个字符是什么。 (1 ≤ n ≤ 1000)
题解：暴力找，n只有1000，来个循环从1开始，整数分解，啪啪啪。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-; int farm(int n){
int i;
for(i=; true; i++){
int j=i,k=;
while(j){
j/=;
k++;
}
if(n>k)n-=k;
else{
if(n==k)return i%;
j=i;
int k2=;
// printf("%d!",j);
while(j){
j/=;
k2++;
if(k-k2==n)return j%;
}
}
}
} int main(){
int n;
RD(n);
WN(farm(n));
return ;
}
B. Different is Good
题意：给出一个小写字母字符串，可以对其中某个位置修改，要求以最少的修改次数，使其所有子串不同，输出修改次数，无解输出-1。
题解：
说是子串不同，其实单个字母就算一个子串，必须使所有字母不同。那超过26的就直接不行，不超过26的，统计各个字母的出现次数。
统计各个字母溢出字数和sum（对有出现的字母，每个字母出现次数-1，加和），统计没有出现的字母的个数last，last大于等于sum就输出sum，否则输出-1。
C. Recycling Bottles
题意：两个人捡垃圾，给出两个人的坐标、垃圾桶坐标、各个垃圾坐标，人有两种选择，可以【不动】，也可以【选一个垃圾，跑去垃圾坐标再跑去垃圾桶坐标】。要捡完所有垃圾，让两个人的行走距离的和最小，输出距离最小值。
题解：主要看第一次捡垃圾，因为之后都是【从垃圾桶走到垃圾，再走回垃圾桶】，所以主要看第一次【从初始坐标走到垃圾】这个能节省多少距离。
这个节省的是【从垃圾桶走到这个垃圾】的时间。
定义Gain = dis(垃圾，垃圾桶) - dis(人，垃圾），Gain越大效果越好，Gain为负数就是反效果。
首先分别对两个人找到他们Gain最高的垃圾和第二高的垃圾，因为他们可能选到同一个垃圾，所以找个第二高的备用。
所以两个人如果有一个Gain为负数，那就只用另一个人捡就行了。两个都为负数，就选个负得少一点的捡。
注意处理选到同一个垃圾的情况，我是分了5种方式，分别是
1.都捡最碉的
2.A捡A的最碉的，B捡B的第二碉的
3.B捡B的最碉的，A捡A的第二碉的
4.A捡最碉，B不捡
5.B捡最碉，B不捡
其中如果两个人选的是一个，就不考虑这个方式。对比各种方式Gain的大小，选最大的，稳。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-;
const double MA=1e10*; const int MAXN=;
int n;
int ax,ay,bx,by,cx,cy;
int X[MAXN],Y[MAXN]; double dis(int x,int y,int x2,int y2) {
LL xx=x-x2;
LL yy=y-y2;
return sqrt(xx*xx+yy*yy);
} double judge(int x,int y,int no) {
if(no==-)return MA;
return dis(X[no],Y[no],cx,cy) - dis(x,y,X[no],Y[no]);
} int findNearest(int x,int y,int &no2) {
int no;
double nd, nd2;
no=;
no2=-;
nd=judge(x,y,no);
nd2=MA;
for(int i=; i<n; i++) {
double d=judge(x,y,i);
if(d>nd) {
no2=no;
nd2=nd;
no=i;
nd=d;
} else if(no2==- || d>nd2) {
no2=i;
nd2=d;
}
}
return no;
} bool ganked[MAXN]; double farm() {
MZ(ganked);
int p[],pp[];
double d[],dd[];
p[]=findNearest(ax,ay,pp[]);
p[]=findNearest(bx,by,pp[]);
int no1[]={p[], p[], pp[], p[], -};
int no2[]={p[], pp[], p[], -, p[]};
int choose=-;
double gain;
int i;
REP(i,){
if(no1[i]==no2[i])continue;
double g = 0.0;
if(no1[i]!=-) g+=judge(ax,ay,no1[i]);
if(no2[i]!=-) g+=judge(bx,by,no2[i]);
if(choose==- || g>gain){
choose = i;
gain = g;
}
}
bool bad[]= {};
int q[] = {no1[choose],no2[choose]};
if(no1[choose]==-)bad[]=;
if(no2[choose]==-)bad[]=;
// cout<<q[0]<<','<<q[1]<<endl;
double re=0.0;
int onex[]={ax,bx};
int oney[]={ay,by};
REP(i,) if(!bad[i]) {
re += dis(onex[i],oney[i],X[q[i]],Y[q[i]]);
ganked[q[i]]=;
}
// cout<<re<<endl;
REP(i,n) {
if(!ganked[i])re += dis(cx,cy,X[i],Y[i])*;
else re+= dis(cx,cy,X[i],Y[i]);
}
return re;
} int main() {
int i;
scanf("%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy);
RD(n);
REP(i,n)RD2(X[i],Y[i]);
printf("%.10f\n",farm());
return ;
}
| D |
standard input/output
1 s, 256 MB |
|
D. Robin Hood
题意：罗宾汉劫富济贫，每天偷最有钱的人一块钱，给最穷的人。有多种选择的话随机偷。给出各个人初始钱数，罗宾汉偷钱天数，输出最后最有钱的人和最穷的人的钱数差。
人数n，天数k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 10^9)
题解：
偷10的9次方天，暴力一天一天偷肯定不行，要想办法一下计算很多天的偷。
我们可以用map来找最穷最有钱的人。map<int,int>，第一个int代表钱数，第二个int代表这个钱数的人数。就叫这个map叫S好了。
每次找到最有钱的人的钱数r，最没钱的人钱数l，一次我们可以帮x个人每个人偷e块钱，操作如下：
S[l]-=x;
S[r]-=x;
如果S[l]或者S[r]为0，就把它从S里删掉。
S[l+e]+=x;
S[r-e]+=x;
这个简单，关键是确定每次的人数x和钱数e。
1.不能偷多，我们不能让最有钱的人们被偷得比第二有钱的人们穷，也不能让最穷的人们比第二穷的人们有钱。所以
e <= min (最有钱的人们的钱数 - 第二有钱人们的钱数 , 第二穷的人们的钱数 - 最穷的人们的钱数)
2.确定人数x，设最穷的人的人数ln，最有钱的人的人数rn，则
x <= min(ln, rn)
3.还要看罗宾汉剩余的天数k，量力而行
e <= k/x
（把x个人每人偷e块钱，需要e*x天，天数要k>=e*x）
如果因为此限制，e必须为0，则说明罗宾汉无力缩小贫富差距了，直接输出当前的贫富差距。
4.如果ln和rn不同，偷完后会剩下abs(rn-ln)人，如果这时k不够了，无法把剩下的人改变e，岂不是贫富差距拉大，所以要
maxX = max(ln, rn)
if(x != maxX){
e=min(k/maxX, e);
e=max(,e);
}
也就是限制e，使得k足够，贫富差距不会拉大。
5.预先可以快速判断是否能将贫富差距缩到最小，也就是算一下钱平均值，然后对每个大于平均值的减去平均值，加和得到sum，也就是拉到平均值所需要的天数，如果罗宾汉天数k大于这个天数，则直接输出(sum%n==0 ? 0 : 1)
（不能整除的话说明最后贫富差距不会缩小到0，最小是1）
大概就是上面这些条件吧，就可以快速地每次把x个人每人偷e块钱，最后他们会越来越多聚集到同一钱数，时间复杂度我也不会算，好像不是很大。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-; const int MAXN=;
int n,k;
int a[MAXN]; int farm() {
int i;
LL sum=;
REP(i,n)sum+=a[i];
double avg = 1.0*sum/n;
int need=;
REP(i,n) {
if(a[i]>avg)need+=ceil(a[i]-avg);
if(need>k)break;
}
if(need<=k)return sum%n==?:;
if(n==)return ;
map<int,int> s;
REP(i,n)s[a[i]]++;
map<int,int>::iterator q,w,q2,w2;
while(k) {
q = s.begin();
w = s.end();
w--;
int l = q->first;
int r = w->first;
if(l==r)break;
q2=q;
w2=w;
q2++;
w2--;
int e,man;
e = min(q2->first - l, r - w2->first);
man = min(q->second, w->second);
e = min(k/man,e);
// printf("%d,%d,%d\n",e,k,man);
if(e==)break;
int maxMan = max(q->second, w->second);
if(man != maxMan){
e=min(k/maxMan, e);
e=max(,e);
}
q->second-=man;
w->second-=man;
if(q->second==)s.erase(q);
if(w->second==)s.erase(w);
k-=e*man;
r-=e;
l+=e;
s[r]+=man;
s[l]+=man; }
q = s.begin();
w = s.end();
w--;
int l = q->first;
int r = w->first;
return r-l;
} int main() {
int i;
RD2(n,k);
REP(i,n)RD(a[i]);
WN(farm());
return ;
}