qzqzgfy's blog

By qzqzgfy, history, 8 years ago, In English

A. Joysticks

================== Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Examples input 3 5 output 6 input 4 4 output 5 It doesn't stop me too much,and the solution is to charge the one with less electricity and discharge the one with more electricity.But the first three times I got f**k in the test No.7 and finally there is a trick(maybe not) that you should break at once the two joysticks are both in 1%.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
long long n,m,cnt;
int main(){
	scanf("%I64d%I64d",&n,&m);
	cnt=0;
	while (1){
	  if (n<=0||m<=0) break;
	  if (n==1&&m==1) break;
	  if (n>m) std::swap(n,m);
	  n+=1;
	  m-=2;
	  cnt++;
	}
	printf("%I64d\n",cnt);
}
B. Beautiful Paintings

================== There are n pictures delivered for the new exhibition. The i-th painting has beauty ai. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that ai + 1 > ai.

Input The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai means the beauty of the i-th painting.

Output Print one integer — the maximum possible number of neighbouring pairs, such that ai + 1 > ai, after the optimal rearrangement.

Examples input 5 20 30 10 50 40 output 4 input 4 200 100 100 200 output 2

Another water problem..,use the counting sort and every time you got a longest monotonic rise sequence a1..ai..an,and the ans+=(n-1),and delete the sequence from the array sorted. when the num of the array is 0,then the ans is the ans.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int n,x,a[1005],cnt,ans;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		a[x]++;
	}
	while (1){
	 if (n==0) break;
	 int cnt=0;
     for (int i=1;i<=1000;i++) if (a[i]) cnt++,a[i]--,n--;
     ans+=cnt-1;
    }
   printf("%d\n",ans); 
}
C. Watchmen

================== Watchmen are in a danger and Doctor Manhattan together with his friend Daniel Dreiberg should warn them as soon as possible. There are n watchmen on a plane, the i-th watchman is located at point (xi, yi).

They need to arrange a plan, but there are some difficulties on their way. As you know, Doctor Manhattan considers the distance between watchmen i and j to be |xi - xj| + |yi - yj|. Daniel, as an ordinary person, calculates the distance using the formula .

The success of the operation relies on the number of pairs (i, j) (1 ≤ i < j ≤ n), such that the distance between watchman i and watchmen j calculated by Doctor Manhattan is equal to the distance between them calculated by Daniel. You were asked to compute the number of such pairs.

Input The first line of the input contains the single integer n (1 ≤ n ≤ 200 000) — the number of watchmen.

Each of the following n lines contains two integers xi and yi (|xi|, |yi| ≤ 109).

Some positions may coincide.

Output Print the number of pairs of watchmen such that the distance between them calculated by Doctor Manhattan is equal to the distance calculated by Daniel.

Examples input 3 1 1 7 5 1 5 output 2 input 6 0 0 0 1 0 2 -1 1 0 1 1 1 output 11

Solution: First,we should know about that : the pair of two points whose Manhattan distance equals to Euclidean distance must be in the same row or the same line.But if two points are in the same coordinate,the we must delete the number that repeated. so the final ans is: ∑the num of the points in same line+∑the num of points in the row- ∑the num of points in the same coordinate.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
struct op{
	long long x,y;
}p[200005];
long long y[200005],x[200005],xx,yy,n,ans,nx[200005],ny[200005];
bool cmp(op q,op w){
    if (q.x==w.x) return q.y<w.y;
	return q.x<w.x;
}
int main(){
	scanf("%I64d",&n);
	for (int i=1;i<=n;i++){
		scanf("%I64d%I64d",&xx,&yy);
		x[++x[0]]=xx;
		y[++y[0]]=yy;
		p[i].x=xx;
		p[i].y=yy;
	}
	std::sort(p+1,p+1+n,cmp);
	std::sort(x+1,x+1+x[0]);
	std::sort(y+1,y+1+y[0]);
	long long tx=1;
	nx[1]=1;
	for (long long i=2;i<=x[0];i++)
	 if (x[i]!=x[i-1]) x[++tx]=x[i],nx[tx]=1;
	 else nx[tx]++;
	x[0]=tx;
	long long ty=1;
	ny[1]=1;
	for (long long i=2;i<=y[0];i++)
	 if (y[i]!=y[i-1]) y[++ty]=y[i],ny[ty]=1;
	 else ny[ty]++;
	y[0]=ty;
	for (long long i=1;i<=x[0];i++)
	 if (nx[i]>1) ans+=(nx[i]*(nx[i]-1))/2;
	for (long long i=1;i<=y[0];i++)
	 if (ny[i]>1) ans+=(ny[i]*(ny[i]-1))/2;
	long long cnt=1; 
	for (long long i=2;i<=n;i++)
	 if (p[i].x==p[i-1].x&&p[i].y==p[i-1].y){
	 	cnt++;
	 }    
	 else{
	 	if (cnt>1) ans-=(cnt-1)*cnt/2;
	 	cnt=1;
	 }
	if (cnt>1) ans-=(cnt-1)*cnt/2;
	printf("%I64d\n",ans); 
}
D. Image Preview

==================

Vasya's telephone contains n photos. Photo number 1 is currently opened on the phone. It is allowed to move left and right to the adjacent photo by swiping finger over the screen. If you swipe left from the first photo, you reach photo n. Similarly, by swiping right from the last photo you reach photo 1. It takes a seconds to swipe from photo to adjacent.

For each photo it is known which orientation is intended for it — horizontal or vertical. Phone is in the vertical orientation and can't be rotated. It takes b second to change orientation of the photo.

Vasya has T seconds to watch photos. He want to watch as many photos as possible. If Vasya opens the photo for the first time, he spends 1 second to notice all details in it. If photo is in the wrong orientation, he spends b seconds on rotating it before watching it. If Vasya has already opened the photo, he just skips it (so he doesn't spend any time for watching it or for changing its orientation). It is not allowed to skip unseen photos.

Help Vasya find the maximum number of photos he is able to watch during T seconds.

Input The first line of the input contains 4 integers n, a, b, T (1 ≤ n ≤ 5·105, 1 ≤ a, b ≤ 1000, 1 ≤ T ≤ 109) — the number of photos, time to move from a photo to adjacent, time to change orientation of a photo and time Vasya can spend for watching photo.

Second line of the input contains a string of length n containing symbols 'w' and 'h'.

If the i-th position of a string contains 'w', then the photo i should be seen in the horizontal orientation.

If the i-th position of a string contains 'h', then the photo i should be seen in vertical orientation.

Output Output the only integer, the maximum number of photos Vasya is able to watch during those T seconds.

Examples input 4 2 3 10 wwhw output 2 input 5 2 4 13 hhwhh output 4 input 5 2 4 1000 hhwhh output 5 input 3 1 100 10 whw output 0

Solution: First we must got to know: it's only once we can swipe from the one side back to the other side,because if we had read the photo,then if we back to the other side then the cost is depend on the length of the path.if we "across over" the photo we had read,then it's only once and if more,it's waste. So we can just pretreat the cost we swipe left and swipe right.And enums to swipe left,and use two pointers to find the how far can I get to the opside with the rest time. If I go right first,then is the same. (I forgot to consider the two situations but the only one yesterday,f**k)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define ll long long
ll l[500005],r[500005],n,a,b,T,cost[500005],ans;
ll find(ll x){
	ll L=2,R=n,res=n;
	if (x<l[n]) return n+1;
	if (x>=l[2]) return 2;
	while (L<=R){
		ll mid=(L+R)/2;
		if (l[mid]<=x) res=mid,R=mid-1;
		else L=mid+1;
	}
	while (x<=l[res]&&res<n+1) res++;
	while (res>2&&x>=l[res-1]) res--;
	return res;
}
ll find1(ll x){
	ll L=2,R=n,res=n;
	if (x<r[2]) return 1;
	if (x>=r[n]) return n;
	while (L<=R){
		ll mid=(L+R)/2;
		if (r[mid]<=x) res=mid,L=mid+1;
		else R=mid-1;
	}
	while (x<r[res]&&res>1) res--;
	while (x>=r[res+1]&&res<n) res++;
	return res;
}
int main(){
	scanf("%I64d%I64d%I64d%I64d",&n,&a,&b,&T);
	char s[500005];
	scanf("%s",s+1);
	for (ll i=1;i<=n;i++)
	 if (s[i]=='w')
	  cost[i]=b+1;
	 else
	  cost[i]=1;
	for (ll i=2;i<=n;i++)
	 r[i]=r[i-1]+a+cost[i]; 
	for (ll i=n;i>=2;i--)
	 l[i]=l[i+1]+a+cost[i];
	for (ll i=n+1;i>=2;i--){
		ll t;
		if (i==n+1)
		t=T-cost[1];
		else
		t=T-l[i]-cost[1]-(n-i+1)*a;
		if (t<0) continue;
		ll x=find1(t);
		ans=std::max(ans,x+(n-i+1));
		if (ans>n) ans=n;
	}
	for (ll i=1;i<=n;i++){
	  ll t;
	  if (i==1)
	  t=T-cost[1];
	  else
	  t=T-r[i]-cost[1]-(i-1)*a;
	  if (t<0) continue;
	  ll x=find(t);
	  ans=std::max(ans,i+n-x+1);
	  if (ans>n) ans=n;
	} 

	printf("%I64d\n",ans);
}
E. Table Compression

==================
Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a' consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a'i, j < a'i, k, and if ai, j = ai, k then a'i, j = a'i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a'i, j < a'p, j and if ai, j = ap, j then a'i, j = a'p, j.

Because large values require more space to store them, the maximum value in a' should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

Examples input 2 2 1 2 3 4 output 1 2 2 3 input 4 3 20 10 30 50 40 30 50 60 70 90 80 70 output 2 1 3 5 4 3 5 6 7 9 8 7

Solution: The last problem.I don't know how to deal with it in exam :| Next day,after consulting others'code,it passed finally. First we sort the n*m numbers in their value. Every time extract the same numbers,union the numbers in same rows or in same lines by using union-find,and find the max number which is in the same row or line to the number of the set.and the ans of the number now I'm solving is the maxinum+1.(My express maybe some kind of ambiguous:)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define N 1000005
struct op{
	int x,y,num;
}f[N];
int tot,go[N],first[N],next[N],n,m,fa[N],a[N],b[N];
bool cmp1(op q,op w){
	return q.x<w.x;
}
bool cmp2(op q,op w){
	return q.num<w.num;
}
bool cmp3(op q,op w){
	return (q.num-1)/m<(w.num-1)/m;
}
bool cmp4(op q,op w){
	return (q.num-1)%m<(w.num-1)%m;
}
int find(int x){
	if (x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}
void insert(int x,int y){
	tot++;
	go[tot]=y;
	next[tot]=first[x];
	first[x]=tot;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n*m;i++){
	 scanf("%d",&f[i].x);
	 f[i].num=i;
	 fa[i]=i; 
    }
    std::sort(f+1,f+1+n*m,cmp1);
    int la=0;
    for (int i=1;i<=n*m;i=la+1){
    	la=i;
		while (f[la+1].x==f[la].x&&la<n*m) la++;
		std::sort(f+i,f+la+1,cmp3);
		for (int j=i+1;j<=la;j++)
		 if ((f[j].num-1)/m==(f[j-1].num-1)/m)
		  fa[find(f[j].num)]=find(f[j-1].num);
		std::sort(f+i,f+la+1,cmp4);
		for (int j=i+1;j<=la;j++)
		 if ((f[j].num-1)%m==(f[j-1].num-1)%m&&find(f[j-1].num)!=find(f[j].num))
		  fa[find(f[j].num)]=find(f[j-1].num);
		for (int j=i;j<=la;j++)
		 insert(find(f[j].num),j);
		for (int j=i;j<=la;j++){
			int o=f[j].num,now=0;
			for (int k=first[o];k;k=next[k]){
				now=std::max(now,std::max(a[(f[k].num-1)/m+1],b[(f[k].num-1)%m+1]));
			}
			for (int k=first[o];k;k=next[k]){
				f[k].y=now+1;
				a[(f[k].num-1)/m+1]=b[(f[k].num-1)%m+1]=now+1;
			}
		}     
    }
    std::sort(f+1,f+1+n*m,cmp2);
    for (int i=1;i<=n;i++){
    	for (int j=1;j<=m;j++)
    	 printf("%d ",f[(i-1)*m+j].y);
    	printf("\n"); 
    }
}

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By qzqzgfy, history, 8 years ago, In English
E. Robot Arm
                             time limit per test8 seconds
                          memory limit per test256 megabytes
                                    inputstandard input
                                    outputstandard output

Roger is a robot. He has an arm that is a series of n segments connected to each other. The endpoints of the i-th segment are initially located at points (i - 1, 0) and (i, 0). The endpoint at (i - 1, 0) is colored red and the endpoint at (i, 0) is colored blue for all segments. Thus, the blue endpoint of the i-th segment is touching the red endpoint of the (i + 1)-th segment for all valid i.

Roger can move his arm in two different ways:

He can choose some segment and some value. This is denoted as choosing the segment number i and picking some positive l. This change happens as follows: the red endpoint of segment number i and segments from 1 to i - 1 are all fixed in place. Imagine a ray from the red endpoint to the blue endpoint. The blue endpoint and segments i + 1 through n are translated l units in the direction of this ray.  In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B gets translated.

He can choose a segment and rotate it. This is denoted as choosing the segment number i, and an angle a. The red endpoint of the i-th segment will stay fixed in place. The blue endpoint of that segment and segments i + 1 to n will rotate clockwise by an angle of a degrees around the red endpoint.  In this picture, the red point labeled A and segments before A stay in place, while the blue point labeled B and segments after B get rotated around point A.

Roger will move his arm m times. These transformations are a bit complicated, and Roger easily loses track of where the blue endpoint of the last segment is. Help him compute the coordinates of the blue endpoint of the last segment after applying each operation. Note that these operations are cumulative, and Roger's arm may intersect itself arbitrarily during the moves.

Input The first line of the input will contain two integers n and m (1 ≤ n, m ≤ 300 000) — the number of segments and the number of operations to perform.

Each of the next m lines contains three integers xi, yi and zi describing a move. If xi = 1, this line describes a move of type 1, where yi denotes the segment number and zi denotes the increase in the length. If xi = 2, this describes a move of type 2, where yi denotes the segment number, and zi denotes the angle in degrees. (1 ≤ xi ≤ 2, 1 ≤ yi ≤ n, 1 ≤ zi ≤ 359)

Output Print m lines. The i-th line should contain two real values, denoting the coordinates of the blue endpoint of the last segment after applying operations 1, ..., i. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 4.

Namely, let's assume that your answer for a particular value of a coordinate is a and the answer of the jury is b. The checker program will consider your answer correct if  for all coordinates.

Examples input 5 4 1 1 3 2 3 90 2 5 48 1 4 1 output 8.0000000000 0.0000000000 5.0000000000 -3.0000000000 4.2568551745 -2.6691306064 4.2568551745 -3.6691306064

:用线段树维护,将相邻两个节点之间向量作为线段树的叶子节点,然后就可以发现(0,0)加上线段树的总和就是N的坐标,接下来就能发现让某个区间的节点绕前一个节点旋转就相当于让这个区间的向量同时旋转这个角度,这相当于区间修改,而移动一个区间就相当于加长一个向量,这相当于单点修改,由于向量可以相加减并且满足交换律,因此用线段树维护是可以保证正确性的。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
#define Rep(i, l, r) for (int i = l; i <= r; ++i)
#define Req(i, l, r) for (int i = l; i >= r; --i)
struct tree{
	double x,y,f;
}t[5000005];
int n,m,opt,pos;
double d,eps=1e-8;
void updata(int k){
	t[k].x=t[k*2].x+t[k*2+1].x;
	t[k].y=t[k*2].y+t[k*2+1].y;
}
double dis(double x,double y){
	return sqrt(x*x+y*y);
}
void pushdown(int k,int l,int r){
	if (l==r) return;
	if (fabs(t[k].f)>eps){
		double ccos=cos(t[k].f),ssin=sin(t[k].f);
		t[k*2].f+=t[k].f;
		t[k*2+1].f+=t[k].f;
		t[k].f=0;
	    double x,y;
	    x=t[k*2].x*ccos-t[k*2].y*ssin;
	    y=t[k*2].x*ssin+t[k*2].y*ccos;
	    t[k*2].x=x;t[k*2].y=y;
	    
	    x=t[k*2+1].x*ccos-t[k*2+1].y*ssin;
	    y=t[k*2+1].x*ssin+t[k*2+1].y*ccos;
	    t[k*2+1].x=x;t[k*2+1].y=y;
	}
}
void build(int k,int l,int r){
	int mid=(l+r)/2;
	if (l==r){
		t[k].x=1.0;
		t[k].y=0.0;
		t[k].f=0;
		return;
	}
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	updata(k);
}
void change(int k,int l,int r,int pos,double d){
	int mid=(l+r)/2;
	pushdown(k,l,r);
	if (l==r){
	    double len=dis(t[k].x,t[k].y);
	    double x=t[k].x/len*d,y=t[k].y/len*d;
	    t[k].x+=x;
	    t[k].y+=y;
	    return;
	}
	if (pos<=mid) change(k*2,l,mid,pos,d);
	else change(k*2+1,mid+1,r,pos,d);
	updata(k);
}
void turn_angle(int k,int l,int r,int x,int y,double d){
	pushdown(k,l,r);
	if (l==x&&y==r){
		double ccos=cos(d),ssin=sin(d);
		double x,y;
	    x=t[k].x*ccos-t[k].y*ssin;
	    y=t[k].x*ssin+t[k].y*ccos;
	    t[k].x=x;t[k].y=y;
	    t[k].f+=d;
	    pushdown(k,l,r);
	    return;
	}
	int mid=(l+r)/2;
	if (y<=mid) turn_angle(k*2,l,mid,x,y,d);
	else
	if (x>=mid+1) turn_angle(k*2+1,mid+1,r,x,y,d);
	else{
		turn_angle(k*2,l,mid,x,mid,d);
		turn_angle(k*2+1,mid+1,r,mid+1,y,d);
	}
	updata(k);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for (int i=1;i<=m;i++){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%d%lf",&pos,&d);
			change(1,1,n,pos,d);
			printf("%.12f %.12f\n",t[1].x,t[1].y);
		}
		else{
			scanf("%d%lf",&pos,&d);
			d=d/(180.0)*acos(-1);
			d=-d;
			turn_angle(1,1,n,pos,n,d);
			printf("%.12f %.12f\n",t[1].x,t[1].y);
		}
	}
}

Full text and comments »

  • Vote: I like it
  • -18
  • Vote: I do not like it

By qzqzgfy, history, 8 years ago, In English
O. Arrow
                         time limit per test0.5 seconds
                        memory limit per test64 megabytes
                             inputstandard input
                            outputstandard output

Petya has recently started working as a programmer in the IT city company that develops computer games.

Besides game mechanics implementation to create a game it is necessary to create tool programs that can be used by game designers to create game levels. Petya's first assignment is to create a tool that allows to paint different arrows on the screen.

A user of this tool will choose a point on the screen, specify a vector (the arrow direction) and vary several parameters to get the required graphical effect. In the first version of the program Petya decided to limit parameters of the arrow by the following: a point with coordinates (px, py), a nonzero vector with coordinates (vx, vy), positive scalars a, b, c, d, a > c.

The produced arrow should have the following properties. The arrow consists of a triangle and a rectangle. The triangle is isosceles with base of length a and altitude of length b perpendicular to the base. The rectangle sides lengths are c and d. Point (px, py) is situated in the middle of the triangle base and in the middle of side of rectangle that has length c. Area of intersection of the triangle and the rectangle is zero. The direction from (px, py) point to the triangle vertex opposite to base containing the point coincides with direction of (vx, vy) vector.

Enumerate the arrow points coordinates in counter-clockwise order starting from the tip.

Input The only line of the input contains eight integers px, py, vx, vy ( - 1000 ≤ px, py, vx, vy ≤ 1000, vx2 + vy2 > 0), a, b, c, d (1 ≤ a, b, c, d ≤ 1000, a > c).

Output Output coordinates of the arrow points in counter-clockwise order. Each line should contain two coordinates, first x, then y. Relative or absolute error should not be greater than 10 - 9.

Examples input 8 8 0 2 8 3 4 5 output 8.000000000000 11.000000000000 4.000000000000 8.000000000000 6.000000000000 8.000000000000 6.000000000000 3.000000000000 10.000000000000 3.000000000000 10.000000000000 8.000000000000 12.000000000000 8.000000000000

大致题意:给出参数和向量方向,求箭头上7个点坐标;

题解:直接运用vx和vy的向量进行装换,由于每次只转90度因此就偷懒用0和1来代替cos90°和sin90°,不过这样也可以避免精度问题。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
double half_pi=acos(-1)/2,px,py,vx,vy,a,b,c,d,vvx,vvy;
double dis(double x,double y){//向量的模
	return sqrt(x*x+y*y);
}
double ccos=0,ssin=1;
void turn_90_degrees(){//旋转向量90°使用的函数
	vvx=vx*ccos-vy*ssin;
	vvy=vy*ccos+vx*ssin;
	vx=vvx;
	vy=vvy;
}
int main(){
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&px,&py,&vx,&vy,&a,&b,&c,&d);
	double D=dis(vx,vy);
	printf("%.12f %.12f\n",px+vx/D*b,py+vy/D*b);
	turn_90_degrees();
	printf("%.12f %.12f\n",px+vx/D*a/2,py+vy/D*a/2);
	printf("%.12f %.12f\n",px+vx/D*c/2,py+vy/D*c/2);
	px=px+vx/D*c/2;py=py+vy/D*c/2;
	turn_90_degrees();
	printf("%.12f %.12f\n",px+vx/D*d,py+vy/D*d);
	px=px+vx/D*d;py=py+vy/D*d;
    turn_90_degrees();
    printf("%.12f %.12f\n",px+vx/D*c,py+vy/D*c);
    px=px+vx/D*c;py=py+vy/D*c;
    turn_90_degrees();
    printf("%.12f %.12f\n",px+vx/D*d,py+vy/D*d);
    px=px+vx/D*d;py=py+vy/D*d;
    for (int i=1;i<=3;i++) turn_90_degrees();
    printf("%.12f %.12f\n",px+vx/D*(a-c)/2,py+vy/D*(a-c)/2);
}

Full text and comments »

  • Vote: I like it
  • -14
  • Vote: I do not like it

By qzqzgfy, history, 8 years ago, In English
P. Area of a Star
                          time limit per test0.5 seconds
                        memory limit per test64 megabytes
                              inputstandard input
                             outputstandard output

It was decided in IT City to distinguish successes of local IT companies by awards in the form of stars covered with gold from one side. To order the stars it is necessary to estimate order cost that depends on the area of gold-plating. Write a program that can calculate the area of a star.

A "star" figure having n ≥ 5 corners where n is a prime number is constructed the following way. On the circle of radius r n points are selected so that the distances between the adjacent ones are equal. Then every point is connected by a segment with two maximally distant points. All areas bounded by the segments parts are the figure parts.

Input The only line of the input contains two integers n (5 ≤ n < 109, n is prime) and r (1 ≤ r ≤ 109) — the number of the star corners and the radius of the circumcircle correspondingly.

Output Output one number — the star area. The relative error of your answer should not be greater than 10 - 7.

Examples input 7 10 output 108.395919545675

这题简直坑爹,要求求中间星星的面积,一开始我用圆形面积减去n个空白处的扇形面积发现精度简直坑爹,直接过不了样例: (过不了样例的程序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
struct Point{
	double x,y;
	Point(){}
	Point(double x0,double y0):x(x0),y(y0){}
}p[5],key,pp;
int n;
double pi,r,rr,s,L,ang;
double dis(Point p1,Point p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
Point inter(Point p1,Point p2,Point p3,Point p4){
	    double a1=p1.y-p2.y;
    	double b1=p2.x-p1.x;
    	double c1=p1.x*p2.y-p1.y*p2.x;
    	double a2=p3.y-p4.y;
    	double b2=p4.x-p3.x;
    	double c2=p3.x*p4.y-p3.y*p4.x;
    	double x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
    	double y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
    	return Point(x,y);
}
int main(){
	freopen("tx.in","r",stdin);
	scanf("%d%lf",&n,&r);
	pi=acos(-1);
	ang=(2*acos(-1))/n;
	p[0].x=r;p[0].y=0.0;
	p[1].x=cos(ang*1)*r;
	p[1].y=sin(ang*1)*r;
    p[2].x=cos(ang*(n/2))*r;
    p[2].y=sin(ang*(n/2))*r;
	p[3].x=cos(ang*(n/2+2))*r;
    p[3].y=sin(ang*(n/2+2))*r;
    pp=inter(p[0],p[2],p[1],p[3]);
    L=ang*r;
    rr=r-sqrt(pp.x*pp.x+pp.y*pp.y);
    s=pi*r*r-(double)(n*rr*L/2.0);
    printf("%lf",s);
 }

 之后我们换种想法,我们可以考虑三角形ABO,我们可以轻松获知角COE为2π/n(因为每个都相等,加起来为圆周), 由圆上角=圆心角的一半可得,∠BAE=π/n,∠BAO=π/2n,且∠BOA为(1/2n)*2π即π/n,已知AO=r,由正弦定理: a/sinA=b/sinB=c/sinC可知BO、AB长度,最终用面积公式S=1/2*a*b*SinC可得答案。 AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int n;
double r;
int main(){
	scanf("%d%lf",&n,&r);
	double A,B,C,a,b,c,s=0;
	a=r;B=acos(-1)/(2*n);C=acos(-1)/n;
	A=acos(-1)-B-C;
	b=a*sin(B)/sin(A);
	s=0.5*a*b*sin(C);
	s=2*n*s;
	printf("%.12f",s);
}

Full text and comments »

  • Vote: I like it
  • -27
  • Vote: I do not like it

By qzqzgfy, history, 8 years ago, In English
E. XOR and Favorite Number
                                       617E
                            time limit per test4 seconds
                        memory limit per test256 megabytes
                                inputstandard input
                                outputstandard output

Bob has a favorite number k and ai of length n. Now he asks you to answer m queries. Each query is given by a pair li and ri and asks you to count the number of pairs of integers i and j, such that l ≤ i ≤ j ≤ r and the xor of the numbers ai, ai + 1, ..., aj is equal to k.

Input The first line of the input contains integers n, m and k (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 1 000 000) — the length of the array, the number of queries and Bob's favorite number respectively.

The second line contains n integers ai (0 ≤ ai ≤ 1 000 000) — Bob's array.

Then m lines follow. The i-th line contains integers li and ri (1 ≤ li ≤ ri ≤ n) — the parameters of the i-th query.

Output Print m lines, answer the queries in the order they appear in the input.

Sample test(s) input 6 2 3 1 2 1 1 0 3 1 6 3 5 output 7 0 input 5 3 1 1 1 1 1 1 1 5 2 4 1 3 output 9 4 4

。。好题,我一开始觉得一定是按分块分的可持久化字典树,具体做法呢就是先利用莫队算法,然后将区间内的所有a[i]都加入字典树,然后对于每个节点我们都有对应能异或得k的所有对应节点,然后我们边修改l和r边修改ans。 然后因为位数在20左右,所以非常完美,不会爆炸。

以上都是yy,其实这题只要用一个sum【i】数组存一个前缀异或和,sum[r]^sum[l-1]就是a[l]到a[r]的异或和了,这样我们每加入一个sum[i]都有对应的op[sum[i]],这样我们再记录一个cnt[i]代表目前a[j]值为i的j的个数 这样ans就能+=cnt[i]*cnt[op[i]],此外,如果k=0,那么便有l=r的情况出现,然而k=0我们只需要特殊处理即可,此题还需要注意longlong,反正我把全部int改成long long了。 代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define ll long long
struct wow{
	ll id,ans,l,r;
}ans[1000005];
ll l,r,mx,a[1000005],block,n,m,k,now,cnt[2000005],sum[1000005],op[2000005],pos[1000005];
bool cmp1(wow q,wow w){
	if (pos[q.l]==pos[w.l]) return q.r<w.r;
	return pos[q.l]<pos[w.l];
}
bool cmp2(wow q,wow w){
	return q.id<w.id;
}
void updata(ll x,ll v){
	if (k!=0)
	now-=cnt[sum[x]]*cnt[op[sum[x]]];
	else
	now-=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;
	cnt[sum[x]]+=v;
	if (k!=0)
	now+=cnt[sum[x]]*cnt[op[sum[x]]];
	else
	now+=((cnt[sum[x]]-1)*(cnt[sum[x]]))/2;
}
int main(){
	//freopen("tx.in","r",stdin);
	scanf("%I64d%I64d%I64d",&n,&m,&k);
	block=sqrt(n);
	for (int i=1;i<=n;i++)
	 pos[i]=i/block;
	for (int i=1;i<=n;i++)
	 scanf("%I64d",&a[i]);
	for (int i=1;i<=n;i++) 
	 sum[i]=sum[i-1]^a[i],mx=std::max(mx,sum[i]);
	for (int i=0;i<=mx;i++)
	 op[i]=i^k;
	for (int i=1;i<=m;i++){
		scanf("%I64d%I64d",&ans[i].l,&ans[i].r);
		ans[i].l--;
		ans[i].id=i;
		ans[i].ans=0;
	}  
	std::sort(ans+1,ans+1+m,cmp1);
    l=ans[1].l;r=ans[1].l;cnt[sum[l]]++;now=0;
    for (int i=1;i<=m;i++){
    	if (l<ans[i].l){
    		for (int j=l;j<ans[i].l;j++)
    		 updata(j,-1);
    	}
    	else
    	if (l>ans[i].l){
    		for (int j=l-1;j>=ans[i].l;j--)
    		 updata(j,1);
    	}
    	l=ans[i].l;
    	if (r<ans[i].r){
    		for (int j=r+1;j<=ans[i].r;j++)
    		 updata(j,1);
    	}
    	else
    	if (r>ans[i].r){
    		for (int j=r;j>ans[i].r;j--)
    		 updata(j,-1);
    	}
    	r=ans[i].r;
		ans[i].ans=now;    
    }
    std::sort(ans+1,ans+1+m,cmp2);
    for (int i=1;i<=m;i++)
     printf("%I64d\n",ans[i].ans);
} 

Full text and comments »

  • Vote: I like it
  • -26
  • Vote: I do not like it