2018年12月

问题描述
  我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
  如果我们把有限小数的末尾加上无限多个0,它们就有了统一的形式。

  本题的任务是:在上面的约定下,求整数除法小数点后的第n位开始的3位数。
输入格式
  一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)
输出格式
  一行3位数字,表示:a除以b,小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914

#include<iostream>
using namespace std;
int main()
{
    long long a,b,n;
    long long sa,sn,count;
    while(cin>>a>>b>>n)
    {
        sn = n;
        sa = a % b;    // 此时的sa*10对b取余后得到小数点后第一位 
        count = 0;
        while(sn--)
        {
            if(sa == b)  //取余之后会等于零 
                break;
            if(sa < b)
            {
                sa = sa * 10;
            }
            else
            {
                //除法法则,逐步运算 
                sa = sa % b;
                sa = sa * 10;
                if(!sa)
                    break;  //后面都是零则直接跳出循环 
                
            }
            count++;
            if(sa % b == a % b) // 减掉循环的数 
            {
                sn = n % count;
            }
        }
        if(!sa)
        {
            cout<<"000";
        }
        else
        {
            int i = 3;
            while(i--)
            {
                cout << sa / b; //逐步输出n后三位的每一位 
                sa = sa % b;
                sa = sa * 10;
            }
        }
    }
    return 0;
}

只运算到n+3w位

可以抽象为无向图染色问题。相邻顶点不能染相同颜色,问至少要用多少种颜色。

问题描述
  n个人参加某项特殊考试。
  为了公平,要求任何两个认识的人不能分在同一个考场。
  求是少需要分几个考场才能满足条件。
输入格式
  第一行,一个整数n(1<n<100),表示参加考试的人数。
  第二行,一个整数m,表示接下来有m行数据
  以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
  一行一个整数,表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;

int gx[106][106];
int js[106][106];
int cnt[106];
int res = 0x3f3f3f3f,n,m;
void dfs(int cur, int tol) {
    if(tol >= res) return;
    if(cur > n) {
        res = min(res, tol);
        return;
    }
 
    for(int i = 0; i < tol; i++) {
        int f = 1;
        for(int j = 0; j < cnt[i]; j++) {
            int t = js[i][j];
            if(gx[cur][t]) {
                f = 0;
                break;
            }
        }
        if(f) {
            js[i][cnt[i]++] = cur;
            dfs(cur+1, tol);
            --cnt[i];
        }
    }
 
    js[tol][cnt[tol]++] = cur;
    dfs(cur+1, tol+1);
    --cnt[tol];
}
int main(int argc, char** argv) {
    scanf("%d%d",&n,&m);
    memset(cnt,0,sizeof(cnt));
    memset(gx,0,sizeof(gx));
    memset(js,0,sizeof(js));
    for(int i = 1;i <= m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        gx[a][b] = 1;
        gx[b][a] = 1;
    }
    dfs(1,0);
    cout << res;
    return 0;
}

注意点:注意开的数组大小为:1000*1000 以上

问题描述
  w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。
  这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。

  如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入格式
  第一行,两个整数m,n,用空格分开,表示格子的行数、列数(1<m,n<1000)。
  接下来一行,一个整数k,表示下面还有k行数据(0<k<100000)
  接下来k行,第行两个整数a,b,表示编号为a的小格子和编号为b的小格子合根了。

  格子的编号一行一行,从上到下,从左到右编号。
  比如:5 * 4 的小格子,编号:
  1 2 3 4
  5 6 7 8
  9 10 11 12
  13 14 15 16
  17 18 19 20
样例输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
样例输出
5

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int parent[10000010],ans = 0;

int find(int x){
    return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void to_union(int x1,int x2){
    int f1 = find(x1);
    int f2 = find(x2);
    if(f1 != f2){
        parent[f2] = f1;
        ans--;
    }
}

int main(int argc, char** argv) {
    int m,n,k,a,b;
    cin >> m >> n;
    cin >> k;
    for(int i = 1;i<=m*n;i++){
        parent[i] = i;
    }
    ans = m*n;
    for(int i = 0;i<k;i++){
        scanf("%d %d",&a,&b);
        to_union(a,b);
    }
    cout << ans << endl;
    return 0;
}

题目描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是 le 50000≤50000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式
输入格式:
11行,若干个整数(个数 le 100000≤100000)

输出格式:
22行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例
389 207 155 300 299 170 158 65

6
2

说明
为了让大家更好地测试n方算法,本题开启spj,n方100分,nlogn200分

每点两问,按问给分

题解(抄别人的)
//我是数据加强以后的第一篇题解(这也是我关于单调性的第一篇题解)这篇有纪念性的文章我要发博客上,不要认为我是复制他人题解

/数据加强到了100000,你要是想得满分200,就必须通过单调性来做(想得100的用n^2算法),而且还要一个神奇的思想(我无法证明),那就是,求一个序列里面最少有多少最长不上升序列等于求这个序列里最长上升序列的长度。我们用f[x]数组(第一问)来记录当前长度为x的不上升序列中最大的结束点(这个运用了贪心的思想),如果当前数小于等于当前的最长不上升序列的结束点,那么我们把当前最长的不上升序列长度加一,把当前数作为这个 不下降序列的结束点,不然我们就用二分查找(为什么可以呢?这是因为我们运用了贪心的思/想后能保证长度越大的不上升序列结束点越小),试着用当前数去更新长度为x的不上升序列的结束点(又是贪心的思想,只更新长度最长且结束点小于自己的),然后第二问你再反着做就行了(把大于等于改为小于)/

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=100005;
int a[maxn];
int f[maxn];
int main()
{
   int n=0;
   int l,r,mid;
   while(scanf("%d",&a[++n])!=EOF)continue;
   n--;
   f[0]=1234123412;//这个数要大于50000,不然可能你就无法更新
   int ans1=0;
   for(int i=1;i<=n;i++){
          if(f[ans1]>=a[i]){
                f[ans1+1]=a[i];//结束点为a[i]
                ans1++; //当前最长不上升序列的长度加一
       }
       else {//二分查找
              l=0;r=ans1;
              while(l<r){
                     mid=(l+r)/2;
                    if(f[mid]>=a[i])l=mid+1;
                    else {
                        r=mid;    
              }
           }
           if(l!=0)f[l]=a[i];
       }
   }
   cout<<ans1<<endl;//输出第一问的答案
     memset(f,-1,sizeof(f));//这次前面要尽量小了,不然又无法更新
   int ans2=0;
   for(int i=1;i<=n;i++){
          if(f[ans2]<a[i]){
                f[ans2+1]=a[i];//结束点为a[i]
                ans2++; //当前最长上升序列长度加一
       }
       else {//二分查找
              l=0;r=ans2;
              while(l<r){
                     mid=(l+r)/2;
                    if(f[mid]>=a[i])r=mid;
                    else {
                        l=mid+1;    
              }
           }
          f[l]=a[i];
       }
   }
   cout<<ans2<<endl;//输出第二个答案
}