2019-08-04 总结

part 1 贪心四题

• 接水问题 重点：time等可能为关键字的单词最好不用，虽然有时在 c++上能过。

代码

• 寻找平面上的极大点 没什么问题

代码

• 守望者的逃离 重点：（1）“&&”（与）的优先级比 “||”（或）的优先级要大，所以有时需要加（）改变优先级
  （2）在最后时，需要仔细分析是需要跑步还需要，不能粗略一笔带过

代码

• 花匠 重点：输入变量是不要用（i , j , k）,一般用（m , n）读入，这样更不容易打错

代码

part 2 2015年普及组

• 求和：主要思路：法一 , 累加式求和，即例如：
  若1号， 3号 ，5号满足条件，他们的分数分别是5 ， 6 ， 7分
  只需算出前面的位置和，分数和，位置*分数和即可
  错误代码（没看出来哪里有问题）

#include<iostream>
#include<cstring>
using namespace std;
long long a[100001] , color[100001];
int tmp[100000] , b[100001] , s[100000] , sum1[3][100000] , sum2[3][100000], sum3[3][100000];
void print ( int a[] , int x)
{
    for ( int i = 1 ; i <= x ; i++)
        cout << a[i] << " " ;
    cout << endl ;
}
int main()
{
    int n , m;
    long long sum = 0;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    for(int i = 1;i <= n;i++)
        cin >> color[i];   
//  print ( a , n) ;
//  print ( color , n) ;
    
        
    for ( int i = 1 ; i <= n ; i++)
        tmp[color[i]]++ ;
    for ( int i = 1 ; i <= m ; i++)
        tmp[i] += tmp[i - 1] ;
//  print ( tmp , m ) ;
    for ( int i = 1 ; i <= m ; i++)
    {
        b[i] = tmp[i] ;
    }
    for ( int i = n ; i > 0 ; i--)
    {
        s[tmp[color[i]]] = i ;
        tmp[color[i]]-- ;
    }
//  print ( s , n) ;
    for ( int i = 1 ; i <= m ; i++)
    {
        
        for ( int j = b[i - 1] + 1 ; j <= b[i] ; j++)
        {
            sum1[s[j] % 2][i] = (sum1[s[j] % 2][i] + s[j] * a[s[j]]) % 10007 ;
            sum += (sum1[s[j] % 2][i] + a[s[j]] * sum2[s[j] % 2][i] + s[j] * sum3[s[j] % 2][i] + a[s[j]] * s[j]);
            sum %= 10007 ;
            sum2[s[j] % 2][i] = ( sum2[s[j] % 2][i] + s[j] ) % 10007 ;
            sum3[s[j] % 2][i] = ( sum3[s[j] % 2][i] + a[s[j]]) % 10007 ;
            
        }
//      cout << sum0[1][i] << " " ;
//      cout << sum1[1][i] << " " ;
//      cout << sum2[1][i] << " " ;
//      cout << sum3[1][i] << " " ;
//      cout << sum0[0][i] << " " ;
//      cout << sum1[0][i] << " " ;
//      cout << sum2[0][i] << " " ;
//      cout << sum3[0][i] << " " ;
    }
    sum %= 10007 ;
    cout << sum ;
    return 0 ; 
}

法二：先将所有东西全加好，再做操作

• 邮递员：改进版：
  思路：选n家，就在前n - 1家的基础上在选一家，分成在最远距离钱和最远距离后分别计算出最大值后比较即可

代码

new question

1.queue() : l( 1 ) , r( 0 ) {}
2.循环队列
3.位运算
C语言位运算符知识总结和实例分析

位运算应用口诀和实例

取模运算总结 - 数论

技巧三.a ^ b ^ b=a

4. image.png

看不懂

RE了四个点 没看出哪里错了
P1739 表达式括号匹配 提交记录

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std ;



const int MAXN = 1e6 ;



char x[MAXN] ;
int m ;
stack<char> s ;
bool check()
{

    for ( int i = 0 ; i < m ; i++)
    {
        if ( x[i] == '(')
        {
            s.push(x[i]) ;
        }
        else
        {
            if ( x[i] == ')' && s.top() != '(')
                return 0 ;
            if ( x[i] == ')')
                s.pop() ;
        }
    }
    if (!s.empty()) 
        return 0 ;
    
    return 1 ;
}

int main()
{
    while(x[m] != '@')
    {
        cin >> x[++m] ;
    } 
    if ( check() == true)
        printf("YES\n") ;
    else 
        printf("NO\n") ;
    return 0 ;
}

6.并查集
并查集例题，想看老师如何写

代码

#include<iostream>
#include<cstdio>

using namespace std ;

int fa[5001] ;

int search(int x)
{
    if ( fa[x] == x) return x ;
    
search(fa[x]) ;
}

void merge(int x , int y)
{
    if ( search(x) == search(y)) return ;
    if ( x > y )
    {
        int t = x ;
        x = y ;
        y = t ;
    }
    fa[search(x)] = y ;
    return ;
}

int n , m , p ; 


int main()
{
    scanf("%d%d%d" , &n , &m , &p) ;//n = 6 , m = 5 , p = 3
    
    
    for ( int i = 1 ; i <= n ; i++)
        fa[i] = i ;
    
    
    for ( int i = 1 ; i <= m ; i++)
    {
        int x , y ;
        scanf("%d%d" , &x , &y) ;
        merge(x , y) ;
    }
    for ( int i = 1 ; i <= p ; i++)
    {
        int x , y ;
        scanf("%d%d" , &x , &y) ;
        if ( search(x) == search(y))
            printf("Yes\n") ;
        else
            printf("No\n") ;
    }
    
    return 0 ;
}

按秩合并

image.png
image.png