【2017四川省赛/牛客】2017 Revenge【数论/指标】

传送门

题意是说给2e6个数,每个数都小于2017,从中选取一些数字使得乘积模2017等于给定的r,问方案数%2输出

DP,f[i][ja[i]%2017]=f[i-1][j]+f[i-1][ja[i]],因为答案只需要奇偶,所以考虑异或操作。

不过这样的复杂度是2017n的。

考虑把乘法变成加法,5是2017的原根,并且2017是质数,剩余系是完全剩余系。所以把1-2016的指标存下来到I[]里面。

f[i][j+I[a[i]]]=f[i-1][j]+f[i-1][j+I[a[i]]]

可以把f开成一个bitset,f[i]表示第i个指标的方案数。所有的状态j每次加一个数I,就相当于循环左移了I位。再用异或滚动状态就可以了。

f^=(f<<I[a[i]])^(f(2016-a[i]))

#include<bits/stdc++.h>
using namespace std;
bitset<2016> f;
int a[2000002], I[2020];
int main()
{
    int n, r;
    int g = 1;
    for(int i = 1; i <= 2016; i++) 
    {
        g = g * 5 % 2017;
        I[g] = i;
    }
    // I[1] = 0;
    while(~scanf("%d%d", &n, &r))
    {
        f.reset();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        f.set(0);
        for(int i = 1; i <= n; i++)
        {
            f 
Read the rest

【最短路/拆点】ACwing176

传送门

把每个点拆成100个点,分别表示到这个点的时候油量剩余的状态。跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int p[maxn], val[maxn], e[maxn], pre[maxn], h[maxn], cnt;
void add(int u, int v, int w)
{
    e[cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt++;
}
struct Ver{
    int a, b, c;
    bool operator<(const Ver &W)const 
    {
        return c > W.c;
    }
};
int dis[1010][110];
bool vis[1010][110];
int dijkstra(int cost, int start, int end)
{
    memset(dis, 0x3f, sizeof dis);
    memset(vis,0, sizeof vis);
    priority_queue<Ver> pq;
    pq.push({start, 
Read the rest

【min_25筛】筛欧拉函数、莫比乌斯函数、积性函数

传送门:欧拉函数、莫比乌斯函数

花了一下午学了一下min25筛。

一知半解。不过还是学会了套板子。

mu函数要看成质数个数取反,在预处理g的时候不能带负数(我也不知道为什么)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
ll primes[maxn], cnt;
bool st[maxn];
ll sp1[maxn], sp2[maxn], g1[maxn], g2[maxn], sm[maxn], g[maxn], w[maxn], wcnt;
ll id1[maxn], id2[maxn];
ll inv2, inv6, qn;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * n;
        n = n * n ;
        k >>= 1;
    }
    return res;
}
void get_primes(int n)
{
    for(int i = 
Read the rest

【树状数组】query

传送门

题意是给一个长度为n的排列。给出m个询问,每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列,n<=1e5,所以用pos[i]存下i这个数的为位置。

nlogn的时间里可以找出所有pair的对数,并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题:L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    
Read the rest

【博弈】HDU 1079 Calendar Game

传送门

题意是说,给定一个日期,每个人可以轮流操作,要么将日期+1变为下一天,要么将日期变为下个月的同一天。

当下个月没有同一天的时候,只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << 
Read the rest

【杜教筛】HUD-6706 huntian oy

传送门

题意:f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(10^9+7)
给定n,a,b求f

打表可知f(n,a,b)=\sum_{i=1}^n \sum_{j=1}^i (i-j)[gcd(i,j)=1]\%(10^9+7)

即:\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ i\ [gcd(i,j)=1]-\sum\limits_{i=1}^n\sum\limits_{j=1}^i\ j\ [gcd(i,j)=1]

在i j互质的时候才有值。前面一部分就是每个数与其互质的个数的和,\sum\limits_{i=1}^{n}i\varphi(i)

后面一部分是每个数,与其互质的数值的和。\sum\limits_{i=1}^{n}\frac{i\varphi(i)}{2}(n1)

原因是gcd(n,x)=gcd(n,n-x),当出现一个与n互质的数x的时候必然有一个n-x成对出现与其互质。他们的和为\frac{n}{2},但这只是在n1的时候成立。

由于n==1的时候只有一个数字1,所以式子完整来写应该是\sum\limits_{i=1}^{n}\frac{i\varphi(i)+1}{2}因为在i=1的时候答案是1,如果除2就成了1/2,所以在分子上加个1使其成立

完整式子是\sum\limits_{i=1}^{n}\frac{i\varphi(i)-1}{2}

由于n有1e9,线筛是存不下的。
考虑
f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

然后套杜教筛的板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
    
Read the rest

【权值线段树】HDU6703-array

传送门

题意是说给定一个排列,长度1e5,要求支持两种操作:
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的,并且大于等于k的,最小的数字。

经过分析,答案最大不可能超过n+1。这样的话,操作1其实相当于把这个数字从排列中删去。

用两棵权值线段树,每个点上存的是位置。

对每次2操作,在[k,n]区间里找最靠左的并且val[x]大于r的数。

对每次1操作,最开始是初始化一颗每个点值都是n+1的权值线段树,删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。

同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。

两个数取最小就是答案。

同时还需记录区间最大最小值,以用来在查询的时候剪枝。

没有这个剪枝,查询会退化为n^2log(n)的,因为区间里可能每个数都会递归到底。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;

struct Node{
    int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
    if(l == r)
    {
        t1[p].l = l, t1[p].r = 
Read the rest

【19HDU多校】Rikka with Coin,贪心

传送门

题意是说有面值10 20 50 100的钱,有n个价格给定的菜,要求用最少的硬币数量,使得所有n个菜品的价格都能被凑出来。

贪心:直观想法是先用大的面值,依次用小的面值。

这样的话可以发现10, 20, 20, 50四个面值能凑出所有100以内的价格。

但是有个例外:90 110 这样的数据,如果按照上面的贪法是100 50 20 20 10五个硬币,实际上只需要50 20 20 20四个硬币就可以拼出来。

所以进一步发现用10 20 20 20 50五个硬币可以包含所有最优方案。两个10肯定能用一个20代替,四个20肯定能用一个50 20 10代替。

所以做一个10 20 20 20 50的子集生成。然后暴力判断dish[i] % 100 + 100dish[i] % 100在某个组合的子集生成里有没有。(有先后顺序,第一个如果有了第二个就不用判断。因为既然零钱数量是固定的,那么100圆的越少约好)如果有,100圆的数量就分别是(dish[i] - (dish[i] % 100 + 100)/ 100) ,和dish[i] / 100

对于100圆判断是个重要细节。
比如1000 90 110这样的数据,1000其中的100圆可以用零钱拼出来,所以100圆个数只有9个。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 
Read the rest

【19牛客多校9_J】Symmetrical Painting【另类扫描线】

传送门

题意是说给n<=3e5条宽度为1的线段,长度不定。

要求一个对称轴,使得将图按照对称轴处理以后剩下的线段最多。

首先猜到的就是对称轴必定出现在某个线段的正中央。但是枚举对称轴以后需要用数据结构维护两边的长度。

有一种离线的做法,更为简单。

  1. 预处理出每条线的 下边线(l)、中线(l+r1)、上边线(r)。
  2. 对于这些预处理出的线,仅仅记录一个y坐标,按照坐标从小到大排序。

  3. 枚举这些线当作对称轴,从下往上做扫描线。线性讨论当前这条线和上一条线之间的线段产生的贡献。也就是当前线为对称轴,上一条线为下半段。按照扫描线一层一层的计算面积贡献。

  4. 在某个线段遇到中线之前,他的面积贡献都是存在的。因为他按照当前扫描线往上翻折,扫描线下方的面积肯定小 于上方,所以贡献是下方面积的两倍 ,于是下边界的贡献flag = 1。

  5. 当扫描线遇到中线的时候,肯定是之前某个线段的中线,此时这条线段在扫描线下方的面积大于等于上方面积,同时这条线段已经达到最大的面积贡献,当扫描线再往上走的时候会减少贡献,每当中线网上移动距离 k 的时候,这条线段就应该减去 2k 的面积贡献。当遇到上边界的时候负贡献消失,变成 0 贡献。于是中线的贡献flag = -2,上边界的flag = 1。

  6. 所以用变量cnt对当前层做出贡献的线段条数,面积和sum每次都+=cnt*(i-last)。然后cnt+=当前层数的贡献。因为兑成轴的只可能产生0.5这种小数,于是为了代码方便,把坐标都扩大两倍,同时计算面积的时候不用乘2。


其实最核心的点就是每当对称轴向上移动k距离的时候,整条线就应该缩短2k的距离,这样才能保证图形是对称的。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 3e5 + 233;
int n;
vector<pii> a;
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        ll l, r;
        cin >> l >> r;
        a.push_back({l * 
Read the rest

【19HDU多校】HDU-6638 Snowy Smile 扫描线/区间连续最大和

传送门

题意很简单,就是求矩阵的最大子矩阵。

数据范围是坐标很多,但是点最多有2000个。100组数据。

根据x坐标排序。对y坐标进行离散化。

枚举x坐标作为左边界,再依次加入某些x相同的点,这样就确定了右边界。

用线段树维护y方向的区间连续最大和。

总体来说就是枚举左右边界,用区间连续最大和来“确定”上下边界。

联动ACWING126

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2002;
typedef long long ll;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define max(a, b) (a) > (b) ? (a) : (b)
struct Node{
    ll l, r, lsum, rsum, sum, dat;
}t[maxn * 4];
void build(ll p, ll l, ll r)
{
    t[p].l = l; t[p].r = r;
    if(l == r) {t[p].lsum = 0, t[p].rsum = 0, t[p].sum 
Read the rest