zkx06111's Blog

//90分，不想改了，用求根公式求两根即可
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

unsigned long long a[3];

string edit(int x) {
	string num="";
	if (x==0) return "x";
	int t=abs(x);
	while (t) {
		num+=t%10+'0';
		t/=10;
	}
	for (int i=0;i<num.size()/2;++i)
		swap(num[i],num[num.size()-i-1]);
	if (x>0) return "(x+"+num+")";
	else return "(x-"+num+")";
	return 0;
}

int main() {
    //freopen("in.txt","r",stdin);
	a[2]=1;
	int x; char c;
	while ((c=getchar())!=EOF) {
		if (c!='+' && c!='-') continue;
		int t; cin>>t; //cout<<'!';
		if (getchar()==EOF) {
			a[0]=t;
			if (c=='-') a[0]*=-1;
            break;
		}
		else {
            if (t==0) a[1]=1;
			else a[1]=t;
			if (c=='-') a[1]*=-1;
		}
	}
	//cout<<a[1]<<' '<<a[0]<<endl;
	int delta=sqrt(a[1]*a[1]-4*a[0]);
	int x2=(-a[1]+delta)/-2,x1=(-a[1]-delta)/-2;
	//cout<<delta<<' '<<x1<<' '<<x2<<endl;
	string s1=edit(x1),s2=edit(x2);
	if (s1==s2) cout<<s1<<"^2";
	else cout<<s1<<s2;
	return 0;
}

//树状数组首杀！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define lowbit(x) ((x)&(-x))
#define MAXN 200005
 
using namespace std;
 
int tree[MAXN],top,n; //tree为树状数组；top为离散化后y的最大值
set<int> out; //out为输出的集合
struct Point {
    int x,y,rk; //x,y为坐标；rk代表按y离散化后的序号；
    int xn,yn; //xn,yn为该点所在横、竖线上点的个数；
    int ans, //ans为以该点来划分，Stan取得个数；
        mn; //mn为画过该点的竖线Stan取得个数的最小值；
}p[MAXN];
 
void add(int x,int v) {
    while (x<MAXN) {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
 
int get(int x) {
    int res=0;
    while (x) {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
 
int get(int x,int y) {
    return get(y)-get(x-1);
}
 
bool cmpy(Point a,Point b) {
    return a.y<b.y;
}
 
bool cmp1(Point a,Point b) {
    if (a.x==b.x) return a.y>b.y;
    return a.x<b.x;
}
 
bool cmp2(Point a,Point b) {
    if (a.x==b.x) return a.y<b.y;
    return a.x>b.x;
}
 
int main() {
    memset(tree,0,sizeof(tree));
    scanf("%d",&n);
    for (int i=0;i<n;++i) {
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].ans=p[i].xn=p[i].yn=0;
    }
    //读入
    sort(p,p+n,cmpy);
    top=1;
    for (int i=0;i<n;++i) {
        if (i && p[i].y!=p[i-1].y) ++top;
        p[i].rk=top; add(p[i].rk,1);
    }
    //离散化
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].y==p[j].y && j<n;++j) ++t;
        for (j=i;p[i].y==p[j].y && j<n;++j) p[i].yn=t;
        i=j-1;
    }
    //计算yn
    sort(p,p+n,cmp1);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(p[i].rk+1,top);
    }
    for (int i=0;i<n;++i) {
        int j,t=0;
        for (j=i;p[i].x==p[j].x && j<n;++j) ++t;
        for (j=i;p[i].x==p[j].x && j<n;++j) p[i].xn=t;
        i=j-1;
    }
    //计算每个点右上方点的个数并同时计算yn
    memset(tree,0,sizeof(tree));
    for (int i=0;i<n;++i) add(p[i].rk,1); //把数组恢复原状
    sort(p,p+n,cmp2);
    for (int i=0;i<n;++i) {
        add(p[i].rk,-1);
        p[i].ans+=get(1,p[i].rk-1);
    }
    //计算每个点左下方点的个数
    for (int i=0;i<n;++i) {
        int j,Min=99999999;
        for (j=i;p[i].x==p[j].x && j<n;++j) Min=min(p[j].ans,Min);
        for (j=i;p[i].x==p[j].x && j<n;++j) p[j].mn=Min;
        i=j-1;
    }
    //计算每条竖线Stan拿到的最小值
    int Max=0; out.clear();
    for (int i=0;i<n;++i) {
        if (p[i].mn!=p[i].ans) continue;
        if (p[i].ans>Max) {
            Max=p[i].ans;
            out.clear();
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1); //Ollie拿到的饼数
        }
        else if (p[i].ans==Max)
            out.insert(n-p[i].ans-p[i].xn-p[i].yn+1);
    }
    printf("Stan: %d; Ollie:",Max);
    for (set<int>::iterator it=out.begin(); it!=out.end();++it)
        printf(" %d",*it);
    printf(";\n");
    return 0;
}

//做法略暴力
#include <iostream>
using namespace std;

int n,a[101][101],l[101],r[101];

void edit(int x) //编辑结点x
{
    int last=0; //上一个x的子结点
    for (int i=1;i<=n;++i)
        if (a[x][i]) {
            if (last) { //若不是第一个结点
                a[x][i]=0;
                a[last][i]=1;
                r[last]=i;
            } //连接上一个结点与该结点，该结点作为上一个结点的右儿子
            else l[x]=i; //第一个结点作为父结点的左儿子
            last=i;
            edit(i); //递归的编辑结点i
        }
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) {
        int t,x; cin>>t;
        for (int j=0;j<t;++j) {
            cin>>x;
            if (x) a[i][x]=1;
        }
    }
    edit(1);
    cout<<n<<endl;
    for (int i=1;i<=n;++i)
        cout<<l[i]<<' '<<r[i]<<endl;
    return 0;
}