A - Relic Discovery
签到
#include <cstdio>
using namespace std;
int T,n;
long long ans=0;
int main()
{
scanf("%d",&T);
for(int t=1; t<=T; t++)
{
scanf("%d",&n);
ans=0;
for(int i=1; i<=n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
ans+=a*b;
}
printf("%lld
",ans);
}
return 0;
}
B - Pocket Cube
直接模拟六种转法。
#include <cstdio>
using namespace std;
int T,n;
long long ans=0;
int st[200];
int t[200];
int check()
{
for (int j = 1; j <= 24; j += 4)
{
int i = j+'a'-1;
if (t[i] != t[i+1] || t[i+1] != t[i+2] || t[i+2] != t[i+3]) return 0;
}
return 1;
}
int mov(char a, char b, char c, char d, char e, char f, char g, char h)
{
int k;
for (int i = 1; i <= 24; i++) t[i+'a'-1] = st[i+'a'-1];
for (int i = 1; i <= 2; i++)
k = t[a], t[a] = t[b], t[b] = t[c], t[c] = t[d], t[d] = t[e], t[e] = t[f], t[f] = t[g], t[g] = t[h], t[h] = k;
if (check()) return 1;
for (int i = 1; i <= 24; i++) t[i+'a'-1] = st[i+'a'-1];
for (int i = 1; i <= 2; i++)
k = t[h], t[h] = t[g], t[g] = t[f], t[f] = t[e], t[e] = t[d], t[d] = t[c], t[c] = t[b], t[b] = t[a], t[a] = k;
if (check()) return 1;
return 0;
}
int main()
{
int T;
scanf("%d", &T);
for (int ca = 1; ca <= T; ca++)
{
for (int i = 1; i <= 24; i++) scanf("%d", &st[i+'a'-1]);
int flag = 0;
for (int i = 1; i <= 24; i++)
t[i+'a'-1] = st[i+'a'-1];
if (check()) flag = 1;
if (mov('a','c','e','g','i','k','m','o')) flag = 1;
if (mov('q','s','g','h','x','v','n','m')) flag = 1;
if (mov('q','r','a','b','u','v','l','k')) flag = 1;
if (flag) printf("YES
");
else printf("NO
");
}
return 0;
}
C - Pocky
记住ln(2)=0.693147。故ans = ln(L) / ln(d)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
for (int ca = 1; ca <= t; ca++)
{
double l, d;
scanf("%lf%lf", &l, &d);
if (l <= d) printf("0.000000
");
else printf("%.6f
", 1+log(l/d));
}
}
D - Lucky Coins
E - Fibonacci
F - Lambda Calculus
G - Coding Contest
H - Pattern
I - Travel Brochure
J - Cliques
K - Finding Hotels
K-d树。题目数据有问题，爆搜也能过。下面的AC代码连样例都过不了。。这数据水的一批。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdlib>
using namespace std;
const int MAXN=2e5+100;
const int DIM=10;
inline double sqr(double x){
return x*x;
}
namespace KDTree{
int K;
struct Point{
int x[DIM];
int price, id;
double distance(const Point& b)const{
double ret=0;
for(int i=0;i<K;i++){
ret+=sqr(x[i]-b.x[i]);
}
return ret;
}
void input(int lll){
id = lll;
for(int i=0;i<K;i++)scanf("%d",&x[i]);
scanf("%d", &price);
}
void output(){
printf("%d %d %d
",x[0], x[1], price);
}
};
struct qnode{
Point p;
double dis;
qnode(){}
qnode(Point _p,double _dis){
p=_p;dis=_dis;
}
bool operator<(const qnode &b)const{
if (fabs(dis-b.dis) < 0.00001) return p.id < b.p.id;
return dis<b.dis;
}
};
priority_queue<qnode>q;
struct cmpx{
int div;
cmpx(const int &_div){
div=_div;
}
bool operator()(const Point &a,const Point &b){
for(int i=0;i<K;i++){
if(a.x[(div+i)%K]!=b.x[(div+i)%K]){
if (a.x[(div+i)%K] !=b.x[(div+i)%K]) return a.x[(div+i)%K]<b.x[(div+i)%K];
return a.id<b.id;
}
}
return true;
}
};
bool cmp(const Point &a,const Point &b,int div){
cmpx cp=cmpx(div);
return cp(a,b);
}
struct Node{
Point e;
Node *lc,*rc;
int div;
}pool[MAXN],*tail,*root;
void init(){
tail=pool;
}
Node *build(Point *a,int l,int r,int div){
if(l>=r)return NULL;
Node *p=tail++;
p->div=div;
int mid=(l+r)/2;
nth_element(a+l,a+mid,a+r,cmpx(div));
p->e=a[mid];
p->lc=build(a,l,mid,(div+1)%K);
p->rc=build(a,mid+1,r,(div+1)%K);
return p;
}
void search(Point p,Node *x,int div,int m){
if(!x)return;
if(cmp(p,x->e,div)){
search(p,x->lc,(div+1)%K,m);
if(q.size()<m){
if (x->e.price <= p.price)
q.push(qnode(x->e,p.distance(x->e)));
search(p,x->rc,(div+1)%K,m);
}else{
if(p.distance(x->e)<q.top().dis){
if (x->e.price <= p.price)
q.pop(), q.push(qnode(x->e,p.distance(x->e)));
}
if(sqr(x->e.x[div]-p.x[div])<q.top().dis){
search(p,x->rc,(div+1)%K,m);
}
}
}else{
search(p,x->rc,(div+1)%K,m);
if(q.size()<m){
if (x->e.price <= p.price) q.push(qnode(x->e,p.distance(x->e)));
search(p,x->lc,(div+1)%K,m);
}else{
if(p.distance(x->e)<q.top().dis){
if (x->e.price <= p.price)
q.pop(), q.push(qnode(x->e,p.distance(x->e)));
}
if(sqr(x->e.x[div]-p.x[div])<q.top().dis)
search(p,x->lc,(div+1)%K,m);
}
}
}
void search(Point p,int m){
while(!q.empty())q.pop();
search(p,root,0,m);
}
};
KDTree::Point p[MAXN];
int main(){
int t;
scanf("%d", &t);
for (int ca = 1; ca<=t; ca++)
{
int n, Q;
scanf("%d%d",&n, &Q);
KDTree::K=2;
for(int i=0;i<n;i++)p[i].input(i);
KDTree::init();
KDTree::root=KDTree::build(p,0,n,0);
KDTree ::Point o;
while(Q--){
o.input(1000000);
int m;
//scanf("%d",&m);
m = 1;
KDTree::search(o,1);
int cnt=0;
while(!KDTree::q.empty()){
p[cnt++]=KDTree::q.top().p;
KDTree::q.pop();
}
//printf(":::::");
p[0].output();
//printf("%d
", p[0].id);
}
}
return 0;
}
L - Tower Attack
M - Generator and Monitor