zkx06111's Blog

//中考考后第一更。我深深地感到自己实在是个大弱逼
//这题代码还是从别人那抄来的。。。
//http://www.cppblog.com/ccl0326/archive/2009/07/31/91792.html
//只好多写点注释，洗清罪名
//这美丽的代码，瞬间自惭形秽
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

string str1;
string str2;
int len1,len2;
int num1,num2;
long StrToInt(string str) //字符串转换+进制转换
{

     long reNum=0;
     int len=str.length();
     int p=0;
     for (int i=len-1;i>=0;i--)
     {
         int u=(int)pow(2,p);p++;
         switch(str[i])
         {
          case '1':reNum+=u;break;
          default:break;
         }
     }
     return reNum;
}
string IntToStr(int value)
{
       string str="";
       while (value!=0)
       {
             int x=value%2;
             if (x==0) str='0'+str; else str='1'+str;
             value=value/2;
       }
       return str;
}
void readp()
{
     cin>>str1;
     cin>>str2;
     num2=StrToInt(str2);
}
void solve()
{
     string str="";
     for (int i=0;i<str1.length();i++)
     {
         str+=str1[i];
         num1=StrToInt(str);
         if (num1>=num2) //把除数扩大10^x倍后再减，提高效率
         {
          int x=num1-num2;
          str=IntToStr(x);
         }
     }
     if (str=="") str="0"; //唯一自己写的一句话，特判
     cout<<str<<endl;
}
int main()
{
    readp();
    solve();

    return 0;
}

//很容易想到要二分，因此关键是求x^x的位数
//x^x的位数=log10(x^x)+1=x*log10(x)+1
#include <iostream>
#include <cmath>
using namespace std;

int main(){
	long long n,l=1,r=2000000000,m;
	cin>>n;
	while (l!=r){
		m=(l+r)>>1;
		long long t=m*log10(m)+1;
		if (t>=n)
			r=m;
		else
			l=m+1;
	}
	cout<<l;
	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;
}