officeyutong

博客

  • ZJOI2014 力

    (其实这道题应该叫强

    其实这就是一道多项式乘法

    题目大意:给出所有的$$q_i(q_i \leq 10^5)$$求$$E_i$$

    其中$$E_i=\sum_{j<i}\frac {q_j} {(j-i)^2}-\sum_{j>i}\frac {q_j} {(j-i)^2}$$

    令n=5 展开式子可得

    $$E_1=0-q_2-q_3*\frac{1}{4}-q_4*\frac{1}{9}-q_5*\frac{1}{16}$$

    $$E_2=q_1-0-q_3-q_4*\frac{1}{4}-q_5*\frac{1}{9}$$

    …(省略)

    $$E_5=q_1*\frac{1}{16}-q_2*\frac{1}{9}-q_3*\frac{1}{4}-q_4-0$$

    然后会发现 式子中的正的那几项恰好是多项式$$q_1+q_2+q_3+q_4+q_5$$与多项式$$0+1+\frac 1 4+\frac 1 9+\frac 1 {16}$$的高次前五项

    而负数部分则是$$-q_5-q_4-q_3-q_2-q_1$$与多项式$$0+1+\frac 1 4+\frac 1 9+\frac 1 {16}$$相乘的第次后五项

    然后加起来即可

    附代码

     

  • 能用的自动AC机

    /*
Automatically AC Program
 * by ???
 * GNU GPL v3
 */
#include <ctime>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include </p>
<map>
#include <windows.h>
#include <fstream>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;
using std::pair;
using std::map;
using std::deque;
using std::ofstream;
using std::ifstream;
//题目名称
const char* appName = "problem";
//测试数据文件夹
const char* dataDir = "data";
//输出文件名
const char* outputName = "problem.out";

ofstream log0("D:/log.txt", std::ios::app);


char buff[512];

char buff0[512];
char sourcePath[1024];
char targetPath[1024];

string path;
int currPos;

const bool FLAG = true;

int main() {
    log0 << "starting" << endl;

    GetModuleFileName(0, buff, 513);
    path = string(buff);
    path = path.substr(0, path.find_last_of("\\"));
    log0 << "running path " << path << endl;

    if (FLAG) {

        currPos = atoi(path.substr(path.find_last_of(".") - 1, 1).c_str()) + 1;
    } else {

    }

    path = path.substr(0, path.find("\\temp"));


    log0 << "current version:" << currPos << endl;
    {
        sprintf(sourcePath, "%s\\%s\\%s\\%s%d.out", path.c_str(), dataDir, appName, appName, currPos);
        GetModuleFileName(0, buff, 513);
        string newpath = string(buff);
        newpath = newpath.substr(0, newpath.find_last_of("\\"));
        sprintf(targetPath, "%s\\%s", newpath.c_str(), outputName);
        log0 << "copying ,source:" << sourcePath << " target " << targetPath << endl;

        CopyFile(sourcePath, targetPath, false);
    }
    {
        sprintf(sourcePath, "%s\\%s\\%s\\%s%d.ans", path.c_str(), dataDir, appName, appName, currPos);
        GetModuleFileName(0, buff, 513);
        string newpath = string(buff);
        newpath = newpath.substr(0, newpath.find_last_of("\\"));
        sprintf(targetPath, "%s\\%s", newpath.c_str(), outputName);
        log0 << "copying ,source:" << sourcePath << " target " << targetPath << endl;

        CopyFile(sourcePath, targetPath, false);
    }

#ifdef PAUSE
    log0 << "pausing" << endl;
    MessageBox(0, "pausing", 0, 0);
#endif
    log0 << "exiting" << endl << endl;
    return 0;
}

     

  • 数论

    x的约数个数

    $$(p_1+1)(p_2+1)(p_3+1)(p_4+1)…..$$

    扩展欧几里得算法

    设$$b\cdot s+(a mod b )t=c$$

    $$\because a mod b =a-(a/b)*b$$

    $$\therefore b\cdot s+(a-(a/b)*b))t=c$$

    $$bs+at-(a/b)bt=c$$

    $$t=\frac {c-bs} {a-(a/b)*b}$$

    中国剩余定理

    解模线性方程组

    所有模数互为质数

    令$$M=m_1m_2m_3….$$

    l $$M_i=M/m_i$$

    $$令t_i 为M_i在模m_i意义下的逆元 即M_i t_i = 1(mod m_i) 那么方程的通解为x=a_1t_1M_1+a_2t_2M_2…………=\sum _{i}a_it_iM_i+kM$$

    卢卡斯定理

    $$n=n_kp^k+n_{k-1}p^{k-1}+…..+n_1p^1+n_0(把n写成p进制数)$$

    $$m=m_kp^k+m_{k-1}p^{k-1}+…..+m_1p^1+m_0(把m写成p进制数)$$

    计算$$C_n^m = (这个不是求和符号,是连乘)\sum_{i=0}^kC_{n_i}^{m_i}(modp) $$

    一些函数

    $$\sum _{d|n} \phi(d)=n$$

    $$\sum _{d|n}\mu(d)=[n=1]=e(n) (单位函数)$$

    $$\phi (p^n)=p^n-p^(n-1)=p^n-不与p互质的数的个数(p的倍数的个数)$$

    $$\phi(n)=\sum _{d|n}d$$

    附图

    数论中的其他一些内容

  • SDOI2010 猪国杀 待填坑

    写一半不想写了 以后想起来再写(可能也没几个以后了

     

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2018年2月20日, 下午5:12
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG
#pragma comment(linker, "/STACK:102400000,102400000")
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;
using std::pair;
using std::map;
using std::deque;

typedef long long int int_t;
class Player;

struct LinkedListNode {
    LinkedListNode* next;
    Player* data;
};
LinkedListNode* head = nullptr;
LinkedListNode* tail = nullptr;
Player* players[11];

enum Type {
    MP, ZP, FP
};

const char CARD_PEACH = 'P';
const char CARD_KILL = 'K';
const char CARD_MISS = 'D';
const char CARD_FIGHT = 'F';
const char CARD_INVASION = 'N';
const char CARD_ARROW = 'W';
//无懈可击 原谅我不会翻译
const char CARD_GOD = 'J';
//猪哥连弩  
const char CARD_GUN = 'Z';

class Player {
private:
    int_t health = 4;
    Type type;
public:
    map cards;

    Player(Type type) :
    type(type) {
    }

    void heal(int_t x) {
        health += x;
        if (health > 4) health = 4;


    }

    int_t getType() {
        return type;
    }

    int_t getHealth() {
        return health;
    }

    bool damage(int_t x) {
        health -= x;
        if (health <= 0) {
            return true;
        }
        return false;
    }

    void play() {

    }
};

namespace card {

    void peach(Player* target) {

    }
}

int main(int argc, char** argv) {

    return 0;
}

  • HDU 2089 不要62

    不要62

    Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 50757    Accepted Submission(s): 19256

    Problem Description
    杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
    杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
    不吉利的数字为所有含有4或62的号码。例如：
    62315 73418 88914
    都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
    你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

     

    Input
    输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

     

    Output
    对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

     

    Sample Input
    1 100 0 0

     

    Sample Output
    80

     

    Author
    qianneng
    地址http://acm.hdu.edu.cn/showproblem.php?pid=2089

    数位DP
    采用记忆化搜索

    $$f(pos,num,less)=0 (num==4时)$$

    $$f(pos,num,less)=0 (less==false且num>arr[pos]时，其中arr是要处理的数的各个数位的数组\ 从高到低排列)$$

    $$f(pos,num,less)=1 (pos==1且num!=4)$$

    $$f(pos,num,less)=\sum _{i=0,num=6与i=2不同时满足}^{9} f(pos-1,i,less||num<arr[pos])$$

    pos:当前要确定的位 从高到低

    num:当前位要搜索的数字

    less:之前的位有没有出现枚举的位比原数中的位小的情况(这样当前位就可以枚举0-9所有的数字 例如枚举上界为15234 那么以15开头只能枚举到15234 而以14开头则能枚举到14999)

    f(pos,num,less) 返回在第pos位上 以num开头 符合条件的数的个数

    最后的结果是

    $$\sum _{i=0}^9 f(pos,i,false)$$

    代码奉上:

     

    // luogu-judger-enable-o2

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/*
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;
using std::pair;
using std::map;
using std::deque;

typedef long long int int_t;
int_t memory[20][20][2];
bool visited[20][20][2];
//第pos为 以num开头的符合要求的数字个数
//less:以前的位是否存在枚举的位比约束小的情况

int_t search1(int_t* arr, int_t pos, int_t num, bool less = false, bool first = true) {
    //    cout << "-----";
//    cout << "searching pos " << pos << " num " << num << " less " << less << endl;
    if (first) {
        memset(visited, 0, sizeof (visited));
    }
    if (num == 4) {
//        cout << "num=4 return0;" << endl;
        return 0;
    }
    if (less == false && num > arr[pos]) {
//        cout << "less=false" << " num=" << num << " arr pos=" << arr[pos] << endl;
        return 0;
    }
    if (pos == 1) {
//        cout << "pos=" << 1 << " return 1 " << endl;
        return 1;
    }
    if (visited[pos][num][less]) {
//        cout << "memory return " << memory[pos][num][less] << endl;
        return memory[pos][num][less];
    }
    int_t result = 0;
    for (int_t i = 0; i <= 9; i++) {
        if (num == 6 && i == 2) continue;
        result += search1(
                arr,
                pos - 1,
                i,
                less || num < arr[pos],
                false
                );

    }

    visited[pos][num][less] = true;
    return memory[pos][num][less] = result;
}

int_t search2(int_t* arr, int_t pos) {
    int_t result = 0;
    for (int_t i = 0; i <= arr[pos]; i++) {
   result += search1(arr, pos, i);
    }
    return result;
}
//没有考虑内存泄漏
int_t* toArray(int_t x) {
    int_t* result = new int_t[10];
    if (x == 0) {
        result[0] = 1;
        result[1] = 0;
        return result;
    }
    result[0] = 0;

    while (x) {
        result[++result[0]] = x % 10;
        x /= 10;
    }
    return result;
}


int main() {
    while (true) {
        int_t lower, higher;
        cin >> lower>>higher;
        if (lower == 0 && higher == 0) return 0;
        int_t* h = toArray(higher);
        int_t* l = toArray(lower - 1);
        cout << search2(h, h[0]) - search2(l, l[0]) << endl;
    }

    return 0;
}

  • 计算几何模板

    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年12月16日, 下午9:52
 */

#include 
#include 
#include 
#include 
#include 
using namespace std;
using real_t = double;
using int_t = long long int;
const real_t EPS = 1e-10;
const real_t PI = acos(-1);

int_t dcmp(real_t a, real_t b) {
    if (abs(a - b) < EPS) return 0;
    else return a - b;
}
struct Point;
typedef Point Vector;

struct Point {
    real_t x;
    real_t y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(real_t x, real_t y) {
        this->x = x;
        this->y = y;
    }
    //返回向量AB

    Vector operator-(Point A) {
        return Vector(x - A.x, y - A.y);
    }
    // 点+向量 返回目标点

    Point operator+(Vector V) {
        return Point(x + V.x, y + V.y);
    }
    //返回*this与v2的数量积

    real_t operator*(Vector v2) {
        return x * v2.x + y * v2.y;
    }
    //返回*this与v2的叉积

    real_t operator^(Vector v2) {
        return x * v2.y - y * v2.x;
    }

    Vector operator*(real_t x) {
        return Vector(this->x*x, this->y * x);
    }

    Vector operator/(real_t x) {
        return Vector(this->x / x, this->y / x);
    }

    bool operator==(Vector vx) {
        return dcmp(x, vx.x) == 0 && dcmp(y, vx.y) == 0;
    }

    real_t length() {
        return sqrt(x * x + y * y);
    }

    Vector rotate(real_t deg) {
        return Vector(x * cos(deg) - y * sin(deg), x * sin(deg) + y * cos(deg));
    }

    Vector normal() {
        real_t len = length();
        return Vector(-y / len, x / len);
    }
    //返回*this与vec之间的夹角
    real_t angleOf(Vector vec) {
        return acos(((*this) * vec) / (length() * vec.length()));
    }

    Vector operator-() {
        return Vector(-x, -y);
    }
};

istream& operator>>(istream& is, Vector& vec) {
    cin >> vec.x >> vec.y;
    return is;
}

ostream& operator<<(ostream& is, Vector vec) {
    cout << "x: " << vec.x << "   y: " << vec.y;
    return is;
}

Vector operator*(real_t x, Vector v) {
    return Vector(v.x*x, v.y * x);
}

Point lineIntersection(Point P, Vector v, Point Q, Vector w) {
    Vector u = P - Q;
    return P + ((w^u) / (v^w)) * v;
}

/*
 * 
 */
int main(int argc, char** argv) {
    int_t x;
    scanf("%lld",&x);
    int_t t;
    cin>>t;
    for (int_t i = 1; i <= t; i++) {
        Point A, B, C;
        cin >> A >> B>>C;
        //向量BC
        Vector BC = C - B;
        Vector CA = A - C;
        Vector BA = A - B;
        real_t CBA = BC.angleOf(BA);
        real_t BCA=(-BC).angleOf(CA);
        Point D = lineIntersection(B, BC.rotate(CBA / 3), C, CA.rotate(BCA * 2 / 3));
        cout << D << endl;
    }
    return 0;
}

  • bzoj 放置士兵

    // luogu-judger-enable-o2
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long int int_t;


struct Edge;
vector edges;
vector graph[20000];
const int_t SOURCE = 0;
const int_t TARGET = 10010;
const int_t V_CNT = 10000;
const int_t HS = 10011;
const int_t HT = 10012;
const int_t INF = 0x7fffffff;
const int_t OFFSET = 1000;

struct Edge {
    int_t from;
    int_t to;
    int_t capacity;
    int_t flow;

    Edge(int_t from, int_t to, int_t capacity, int_t flow) {
        this->flow = flow;
        this->from = from;
        this->to = to;
        this->capacity = capacity;

    }
};

inline void pushEdge(int_t from, int_t to, int_t capacity) {
    cout << "pushing edge " << from << " " << to << " " << capacity << endl;

    edges.push_back(Edge(from, to, capacity, 0));
    edges.push_back(Edge(to, from, 0, 0));
    graph[from].push_back(edges.size() - 2);
    graph[to].push_back(edges.size() - 1);
}

inline void pushLowerBoundEdge(int_t from, int_t to, int_t lowCap, int_t highCap) {
    cout << "pushing lower bound edge " << from << " " << to << " lowCap" << lowCap << " highCap" << highCap << endl;

    pushEdge(from, to, highCap - lowCap);
    pushEdge(from, HT, lowCap);
    pushEdge(HS, to, lowCap);
}



namespace dinic {
    int_t dis[V_CNT + 1];
    bool visited[V_CNT + 1];
    int_t curr[V_CNT + 1];

    bool BFS() {
        queue qu;
        memset(visited, 0, sizeof (visited));
        memset(dis, 0x7f, sizeof (dis));
        visited[SOURCE] = true;
        dis[SOURCE] = 0;
        qu.push(SOURCE);
        while (qu.empty() == false) {
            int_t front = qu.front();
            qu.pop();
            for (int_t i = 0; i < graph[front].size(); i++) {
                int_t x = graph[front][i];
                Edge& edge = edges[x];
                if (edge.flow < edge.capacity && visited[edge.to] == false) {
                    visited[edge.to] = true;
                    dis[edge.to] = dis[front] + 1;
                    qu.push(edge.to);
                }
            }

        }
        return visited[TARGET];
    }

    int_t DFS(int_t pos, int_t minFlow = 0x7ffffffff) {
        if (pos == TARGET || minFlow == 0) return minFlow;
        int_t flow = 0;
        for (int_t& x = curr[pos]; x < graph[pos].size(); x++) {
            int_t & edgeID = graph[pos][x];
            Edge& edge = edges[edgeID];
            if (dis[edge.to] == dis[pos] + 1) {
                int_t f = DFS(edge.to, std::min(minFlow, edge.capacity - edge.flow));
                if (f > 0) {
                    flow += f;
                    minFlow -= f;
                    edge.flow += f;
                    edges[edgeID^1].flow -= f;
                    if (minFlow == 0) break;

                }
            }
        }
        return flow;
    }

    int_t maxFlow() {
        int_t result = 0;
        while (BFS()) {
            memset(curr, 0, sizeof (curr));
            int_t x = DFS(SOURCE);
            if (x == 0) break;
            cout << x << endl;
            result += x;
        }
        return result;
    }
}
int_t minFlow[100000 + 1];
int_t path[100000 + 1];

int_t EdmondsKarp() {
    int_t maxFlow = 0;
    while (true) {
        //BFS
        queue qu;
        qu.push(SOURCE);
        memset(minFlow, 0, sizeof (minFlow));
        minFlow[SOURCE] = 0x7fffffff;
        memset(path, 0, sizeof (path));
        while (qu.empty() == false) {
            int_t x = qu.front();
            qu.pop();
            cout << "poping " << x << endl;

            for (int_t i=0;i> m >> n>>k;
    for (int_t i = 1; i <= m; i++) cin >> requireL[i];
    for (int_t i = 1; i <= n; i++) cin >> requireC[i];
    for (int_t i = 1; i <= k; i++) {
        {
            int_t x, y;
            cin >> x>>y;
            board[x][y] = 0;
            placableL[x]--;
            placableC[y]--;

        }
    }
    for (int_t i = 1; i <= m; i++) {
        placableL[i] += n;

        if (placableL[i] < requireL[i]) fail();
    }
    for (int_t i = 1; i <= n; i++) {
        placableC[i] += m;
        if (placableC[i] < requireC[i]) fail();
    }
    for (int_t i = 1; i <= m; i++) {
        pushEdge(SOURCE, i, placableL[i] - requireL[i]);
    }
    for (int_t i = 1; i <= n; i++) {
        pushEdge(i + OFFSET, TARGET, placableC[i] - requireC[i]);
    }
    int_t x = 0;
    for (int_t i = 1; i <= m; i++) {
        for (int_t j = 1; j <= n; j++) {
            if (board[i][j]) {
                x++;
                pushEdge(i, j + OFFSET, 1);
            }
        }
    }
   // cout << "x=" << x << endl;
    //cout << "maxflow" << EdmondsKarp() << endl;

    cout << x - EdmondsKarp() << endl;

    return 0;
}

  • 单纯型法

    会了，不写。

  • 图论

    在无向图中

    点双连通分量：
    去掉一个点，不会把图分成两个不同的部分
    边双联通分量：
    去掉一条边，不会把图分成两个部分

    k点连通分量：去掉k个点，图才能变成多个连通分量

    k边连通分量：去掉k条边，图才能变成多个连通分量

     

     

    上下限网络流

    某边有流量上下限 上限照旧

    建立HyperS HyperT

    连一条边从T到S 容量INF

    有下界的边 容量下界变为0 上界变为原来的上界-下界

    起点连到HT 容量为下界

    ST连到终点 容量为下界

  • Merging and spliting based BST

    // luogu-judger-enable-o2

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/*
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::max;
using std::min;
using std::sort;
using std::pair;

using int_t = int;
const int_t LARGE = 500000;
const int_t MIN = -2147483647;
const int_t INF = 2147483647;

struct Node {
    int_t value;
    int_t count = 0;
    int_t size = 0;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(int_t val) :
    value(val) {
        count = 1;
        size = 1;
    }

    void maintain() {
        size = count;
        if (left) size += left->size;
        if (right) size += right->size;
    }

    int_t leftSize() {
        if (left) {
            return left->size;
        } else {
            return 0;
        }
    }
};
//const int_t _NODE_MAX = LARGE * 2;
//char buff[sizeof (Node) * _NODE_MAX];
//int_t used = 0;

Node* nextNewNode(int_t val) {
    //    Node* x;
    //    if (used < _NODE_MAX - 1) {
    //        x = new (buff + sizeof (Node)*(used++))Node(val);
    //    } else return new Node(val);
    return new Node(val);
}

//将left和right两棵树合并
//不会对原树做出更改

Node* merge(Node* left, Node* right) {
    if (left == nullptr) return right;
    else if (right == nullptr) return left;
    else {
        int_t opt = rand() % 2;
        if (opt == 0) {
            left->right = merge(left->right, right);
            left->maintain();
            return left;
        } else {
            right->left = merge(left, right->left);
            right->maintain();
            return right;
        }
    }
}
//将root分裂成两棵树,左边的树包含leftSize个节点
//会对原树做出更改

pair split(Node* root, int_t leftSize) {
    if (root == nullptr) return std::make_pair(nullptr, nullptr);
    else if (root->leftSize() == leftSize) {
        Node* bak = root->left;
        root->left = nullptr;
        root->maintain();
        return std::make_pair(bak, root);
    } else if (leftSize < root->leftSize()) {
        auto result = split(root->left, leftSize);
        Node* newRoot = root;
        newRoot->left = result.second;
        newRoot->maintain();
        return std::make_pair(result.first, newRoot);
    } else {
        auto result = split(root->right, leftSize - root->count - root->leftSize());
        Node* newRoot = root;
        newRoot->right = result.first;
        newRoot->maintain();
        return std::make_pair(newRoot, result.second);
    }
}

int main() {
    
}