SDUT 2018 Winter Individual Contest - 7

比赛链接
比赛密码: pojianchengdie

dp再继续
题目链接
题目大意:长度为n的数列，满足任意连续长度为k的串乘积都为正数
题目关键：
序号相差k的数字，满足题中式子时正负性一定相等。
可以举例验证 1 -2 -1 3 4 -1 (k = 3) 把4改成-4一定满足
然后递推即可，num[i][0]表示所有下标模k 的数组a中为正数的个数，递推式的含义大概如下，正数（到i为止） =min（ 正数（到i-1为止）+ 到i为止负数的个数 （即把负数变为正数），负数（到i-1为止）+到i为止正数的个数（即把正数变为负数））;

#include <cstdio>
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <math.h>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=5e5+7;
int num[maxn][4];
int dp[maxn][2];
int n,k;
int main() {
     cin>>n>>k;
     for(int i=0;i<n;i++)
     {
         int temp;
         cin>>temp;
         ++num[i%k][temp<0];
     }
     dp[0][0] = num[0][0];
     dp[0][1] = num[0][1];
     for(int i=1;i<k;i++)
     {
         dp[i][0] = min(dp[i-1][0]+num[i][1],dp[i-1][1]+num[i][0]);
         dp[i][1] = min(dp[i-1][1]+num[i][1],dp[i-1][0]+num[i][0]);
     }
     cout<<dp[k-1][1]<<endl;
    return 0;
}

H 二位树状数组
题意：
事情是，GEMA探险家是高度熟练的科学家，讨厌小工作，但有人必须这样做。玛格丽达被选为主要研究实验室的地板。她非常狡猾懒惰，所以她解释说明的方式，她会检查矩形的左边界，如果所有的瓷砖都画了，她不会画任何瓷砖。另外，如果左边框中有未上漆的图块，她将绘制从该图块到达的所有未上漆的图块。如果可以使用矩形内唯一没有涂漆的瓷砖到达，则可以从另一个瓷砖到达另一个瓷砖。
输入矩阵大小n,m,h,w,q
接下来q行
每行一个点，把从当前点开始大小为h*w的矩阵涂色，
问没输入一个点后矩阵中为涂颜色的点还有多少？
题目解析：用一个数组a来模拟矩阵，ans用来维护当前答案，要涂的点肯定是无法避免的，因此我们要尽可能的减少重复的涂色，因此dfs+标记数组还不够，我们利用树状数组来记录一列已经涂过色的个数如果等于h，那么说明该列已经被涂过了，根据题意就不用再涂了，为了方便计算某一列的已经涂过的格数，我们这里把二维树状数组进行了转置，具体可以打印出来看下

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const int maxn  = 99999;
vector<int>c[100999];
vector<int>a[100999];
int v[]= {0,0,1,-1};
int u[]= {1,-1,0,0};
int n,m,lx,ly,rx,ry,ans;
void add(int y,int x)
{
    while(y<=n)
    {
        c[x][y]++;
        y+=y&(-y);
    }
}
int sum(int y,int x)
{
    int as = 0;
    while(y)
    {
        as+=c[x][y];
        y-=y&(-y);
    }
    return as;
}
void pt(int x,int y)
{

    if(a[x][y]==1)
        return ;
//    cout<<x<<" # "<<y<<endl;
    a[x][y] = 1;
    ans--;
    add(x,y);
    for(int i=0; i<4; i++)
    {
        int p = x+v[i],q = y+u[i];
        if(p>=lx&&p<=rx&&q>=ly&&q<=ry)
            pt(p,q);
    }
}
int main()
{
    int h,w,q;
    cin>>n>>m>>h>>w>>q;
    ans = n*m;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=m; j++)
        {
            a[i].push_back(0);
        }
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=0; j<=n; j++)
        {
            c[i].push_back(0);
        }
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        lx = x,ly = y;
        rx = x+h-1;
        ry = y+w-1;
        if(sum(rx,y)-sum(x-1,y)!=h)
        {
            for(int i=x; i<=rx; i++)
            {
                if(a[i][y]==0)pt(i,y);
            }
        }
//        for(int  i=1; i<=m; i++)
//        {
//            for(int j=1; j<=n; j++)
//            {
//                printf("%d ",c[i][j]);
//            }
//            printf("\n");
//        }
//        printf("\n");
//        for(int i=1; i<=n; i++)
//        {
//            for(int j=1; j<=m; j++)
//            {
//                printf("%d ",a[i][j]);
//            }
//            printf("\n");
//        }
//        printf("END\n");
        cout<<ans<<endl;
    }


    return 0;
}

g
K. Dire, Dire Docks
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
Half a century after the Mars arrival by GEMA, we are finally here. The mission is finally starting to build artificial rivers on mars.

That is possibly the most important event on Mars since the GEMA arrival.

In order to carry on with it, the mission have mapped the surface as 2-dimensional plane, and has identified N points in it that are going to work as reference points to build a river system. There will be a dock constructed in each of these points to help on transportation efforts and collect data for the mission.

The goal of the mission is to connect all the docks with rivers. The lead researcher of the team responsible for that, doctor Maya Waters, has identified the main requirements to build a healthy river system. These are:

There are N docks. There should be a way to navigate between any two docks only through water;
The system must have exactly N rivers - no more, no less;
At most four rivers can meet at any single dock;
Any river should flow in a straight line between points A and B;
There should be no river crossings apart from the rivers meeting at docks. Note that a river passing through a dock counts as a crossing.
Help doctor Maya figure out which points to connect to build such river system and finally Make Mars Wet Again!

Input
Input begins with N (3 ≤ N ≤ 103), the number of points. Follows N lines, each with two integers xi, yi( - 109 ≤ xi, yi ≤ 109), the coordinates of the pivotal points.

Output
Output N lines. In each line, output two integers , a and b - the indexes of the pivotal points that must be connected by a river. Indexing begins in 1. If there are multiple solutions, output any.

If it is an impossible task, output -1.

Examples
input
5
-1 0
2 3
3 2
5 4
6 1
output
3 2
3 4
5 3
1 5
2 4
input
3
0 0
1 2
3 6
output
-1
除了所有点在一条直线，其他情况都有解。
先按坐标排个序，按顺序连起来，再找一条线就可以。剩下的一条线，一端为第一个点，依次枚举。

B：
输入m行每行都是7个音符，每个人都可以任选两行当作是他会的谱子。这个人弹过之后，就不能再弹了，现在输入一个有n个音符的曲子，求最少几个人可以把这只曲子谈完

#include <cstdio>
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <math.h>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=5e5+7;
int num[maxn][4];
int dp[maxn][2];
int n,k;
int toint(char *s)
{
    int ans =0 ;
    ans = (s[0]-'a')*3;
    if(s[1]==0)return ans;
    else if(s[1]=='b')ans++;
    else if(s[1]=='#')ans+=2;
    return ans;
}
int all[20];
int main() {
     int n,m;
     while(cin>>m)
     {
         char temp[10];
         memset(all,0,sizeof all);
         for(int i=0;i<m;i++)
         {
             for(int j=0;j<7;j++)
             {

                 scanf("%s",temp);
                 all[i]|=(1<<toint(temp));
             }
         }
         cin>>n;      
        int qu[12345];
        memset(qu,0,sizeof qu);
         for(int i=0;i<n;i++)
         {
              scanf("%s",temp);
              qu[i] = toint(temp);
         }
         int ans =0 ;
         for(int i=0;i<n;)
         {
             int point = 0;
             for(int j=0;j<m;j++)
             {
                 for(int k=0;k<m;k++)
                 {
                     int pp = i;
                     while(all[j]&(1<<qu[pp])||all[k]&(1<<qu[pp]) )
                           {
                               if(pp<=n)pp++;
                                else break;
                           }
                    point = max(point,pp);
                 }
             }
             i = point;
             ans++;
         }
         cout<<ans<<endl;

     }
    return 0;
}