Test on 11/09/2016

@kaike

尽管我们手中空无一物，却能因此紧紧相连。

1．质数

  (prime.pas/c/cpp)

【问题描述】

    质数也叫素数，指除了1和它本身没有其他因子的整数。

    质数是数论中很特殊的数，作用也很大，小x也在研究。

    小x对小y说，你给我一个数字，我可以告诉你这个数字是不是质数。读题的你肯定很不屑小x的自大，这个还用说，只要学习OI的都会。

    那么小x的问题就改为：给你一个区间[X,Y]，问从X到Y有多少个质数。

【输入】

       两个整数X和Y。保证 X<=Y。

【输出】

一个整数，表示X到Y有多少个质数。

【输入输出样例】

prime.in	prime.out
2 11	5

【数据范围】

有部分数据保证 Y-X<=10000  

100% 数据 X<=Y<=2147483647 (int 的最大值)  Y-X<=1000000

想着说把所有素数全求出来，用前缀和，

后来数据太大，不可能以O(N*N)的计算量算出来

就去网上找了线性筛法。

后来又因为一个优化，应该吧 50000 以内的素数算出来，然后将 l-r 的合数筛掉

就这样只有40qaq,关键是40我还不会qaq

每次都觉得自己代码low爆了，别人代码都炒鸡好看怎么破

先附上40分

/*
by kaike
11/09/2016
*/
#include <iostream>
#include <cstdio>
using namespace std;
int prime[99999999];        
bool is_prime[99999999];   
int xx,yy; 
int slove(int n)
{
    int p = 0;
    for(int i=0; i<=n;i++)
        is_prime[i] = true;             
    is_prime[0] = is_prime[1] = false;    
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])                
        {
            prime[p++] = i;
            for(int j=2*i; j<=n; j+=i)    
                is_prime[j] = false;
        }
    }
    return p;
}
int main()
{
    freopen("prime.in","r",stdin);
    freopen("prime.out","w",stdout);
    cin>>xx>>yy;
    cout <<slove(yy)-slove(xx-1)<< endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

后来模仿jjh的代码过了60？

wtf？从两点调到了五点。我也不想说什么了

后来发现数据从int到了long long 成功过了。

/*
by kaike
11/10/2016
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
#define FILE "prime"
const int MAXN=1000005;
const int LIM=50000;
const int oo=2147483647;
int x,y;
int p[MAXN],cot=0,ans=0;
bool vis[MAXN];
void init()
{
    cin>>x>>y;
    for(long long i=2;i<=LIM;i++)
    {
        if(!vis[i])   p[++cot]=i;
        for(long long j=1;j<=cot;j++)
        {
            if(i*p[j]>LIM)  break;
            vis[i*p[j]]=1;
            if(i%p[j]!=0)   break;
        }
    }
}
void work()
{
    memset(vis,0,sizeof(vis));
    for(long long i=1;i<=cot;i++)
         for(long long j=x/p[i];j<=oo;j++)
        {
            if(j*p[i]>y)    break;
            if(j*p[i]<x)    continue;
            if(j>1)
            {
                if(!vis[j*p[i]-x])    ans++;
                vis[j*p[i]-x]=1;
            }
        }
    if(x==1)    ans++;
    cout<<y-x+1-ans<<endl;
}
int main()
{
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    init();
    work();
    return 0;
}

2．飞天

  (sky.pas/c/cpp)

【问题描述】

    小x和他的小伙伴们创作了一个舞蹈——飞天。

    这个舞蹈由N个小朋友一起来完成，编号分别为[1..N]。每位小朋友都被威亚吊着飞在天空中，每个人的高度为H[i],做着各种高难度动作。

    小x作为导演，又有了新的想法，他把舞蹈分为M大部分。每部分只挑选编号连续的某些小朋友，升到相同的高度，做相应的表演。等本部分表演结束，小朋友的高度会自动恢复到原来的高度。

    但是，现在每次调整高度难坏了小x，并且每位选手调整的高度增加或减少1，小x就要花费单位为1的能量，小x就想知道，怎么安排调整高度，能让自己消耗的能量最少。

【输入】

第一行为两个正整数n、m。

第二行共n个非负整数，表示第i位小朋友的高度h[i]。

接下来m行每行2个整数L_i、R_i（L_i≤R_i）。 表示要调整编号为[Li,Ri]的高度

【输出】

一个整数，表示调整高度的最小能量消耗。

【输入输出样例1】

sky.in	sky.out
6 4 4 1 2 13 0 9 1 5 2 6 3 4 2 2	48

【样例解释】

 第一次调整编号为1..5的小朋友，如果把高度都调整为2，那么消耗能量为2+1+0+11+2=16。这个是最小的。

第二次调整编号为2..6的小朋友，能量值消耗最小为21。

第三次消耗为11。第四次消耗为0。

总消耗为48。

【数据范围】

对于50％的数据 n≤500，m≤1000；

对于80％的数据 n≤1000，m≤100000；

对于100％的数据n≤1000，m≤200000;

答案小于2^64。

我能说我真没想到中位数么，第一感觉woc它咋知道这数的，第二感觉这肯定是二分找数对没错

于是华丽丽的交上去

20

don't want to say what。

先来个70，没什么可说的注意long long ，找中位数而已。

/*
by kaike
11/10/2016
*/
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
using namespace std;
#define FILE "sky"
int n,m,h[1100],x,y,b[1100];
long long ans=0;
void init()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>h[i];    
}
void work()
{
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if(x==y)    continue;
        for(int j=1;j<=y-x+1;j++)
            b[j]=h[x+j-1];
        sort(b+1,b+y-x+2);
        int t;
        if((y-x+1)%2==0)    t=b[(y-x+1)/2];
        else    t=b[(y-x+1)/2+1];
        for(int j=x;j<=y;j++)
            ans+=abs(h[j]-t);
    }
    cout<<ans<<endl;
}
int main()
{
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
    init();
    work();
    return 0;
}

1．树

  (tree.pas/c/cpp)

【问题描述】

 Fanvree很聪明，解决难题时他总会把问题简单化。

例如，他就整天喜欢把图转化为树。但是他不会缩环，那他怎么转化呢？

这是一个有n个点m条双向边的图，Fanvree会选定一个节点，然后删掉这个节点和这个点连出去的边，如果变成了一棵树，那么这个节点便是可行的，什么是树呢？树也即无简单环的无向连通图。

现在你需要告诉Fanvree可能的节点是什么。

【输入】

第一行两个正整数 n,m，表示有 n 个点 m 条边。保证 n≥2。

接下来 m 行，每行两个整数 v,u，表示 v 和 u 之间有一条无向边 1≤v,u≤n。保证 没有重边和自环。

【输出】

第一行一个正整数 ns，表示这个图中有 ns 个结点可选。

接下来一行，共 ns 个整数，每个整数表示一个可选结点的编号。请按编号从小 到大的顺序输出。

数据保证图中至少存在一个可选的结点。

【输入输出样例1】

tree.in	tree.out
6 6 1 2 1 3 2 4 2 5 4 6 5 6	3 4 5 6

【数据范围】

   对于40%的数据，n,m<=1000 另存在10%的数据，m=n-1

另存在20%的数据，m=n

对于100%的数据，n,m<=100000 

这题就是找割点，在把可以构成环的删掉...不会环...割点还好吧...