Skip to content

Latest commit

 

History

History
273 lines (242 loc) · 6.72 KB

0-杂项.md

File metadata and controls

273 lines (242 loc) · 6.72 KB
Raw

0-杂项

快读

inline int read()
{
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
        if (ch == '-')
        {
            w = -1;
        }
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * w;
}

judge.sh

Assume using directory "./contest".

../contest:
a.cpp  b.cpp  samples-a  samples-b  judge.sh

../contest/samples-a:
1.ans  1.in

../contest/samples-b:
1.ans  1.in  2.ans  2.in

judge.sh

#!bin/bash
set -e
[ $# == 2 ] || { echo invalid args ; exit 1 ; }
g++ $2.cpp || { echo CE ; exit 1 ; }
src=./samples-$1
dir=$1-test
mkdir -p $dir
cp $src/* $dir/ 
cd $dir
mv ../a.out ./$2
for input in *.in; do
  [ $input == "*.in" ] && exit 0
  cas=${input%.in}
  output=$cas.out
  answer=$cas.ans
  timeout 1 ./$2 < $input > $output 2> $cas.err || { echo Case $cas : TLE or RE ; continue ; }
  if diff -Za $output $answer > $cas.dif ; then
    echo Case $cas : AC
  else
    echo Case $cas : WA
    cat $cas.dif $cas.err
  fi
done

command:

cd ./contest
bash judge.sh a a.cpp

心态崩了

  • (int)v.size()
  • 1LL << k
  • 递归函数用全局或者 static 变量要小心
  • 预处理组合数注意上限
  • 想清楚到底是要 multiset 还是 set
  • 提交之前看一下数据范围，测一下边界
  • 数据结构注意数组大小 （2倍，4倍）
  • 字符串注意字符集
  • 如果函数中使用了默认参数的话，注意调用时的参数个数。
  • 注意要读完
  • 构造参数无法使用自己
  • 树链剖分/dfs 序，初始化或者询问不要忘记 idx, ridx
  • 排序时注意结构体的所有属性是不是考虑了
  • 不要把 while 写成 if
  • 不要把 int 开成 char
  • 清零的时候全部用 0~n+1。
  • 模意义下不要用除法
  • 哈希不要自然溢出
  • 最短路不要 SPFA，乖乖写 Dijkstra
  • 上取整以及 GCD 小心负数
  • mid 用 l + (r - l) / 2 可以避免溢出和负数的问题
  • 小心模板自带的意料之外的隐式类型转换
  • 求最优解时不要忘记更新当前最优解
  • 图论问题一定要注意图不连通的问题
  • 处理强制在线的时候 lastans 负数也要记得矫正
  • 不要觉得编译器什么都能优化
  • 分块一定要特判在同一块中的情况
  • priority_queue<ll>是大根堆,每次取出最大。小根堆是priority_queue<ll,vector<ll>,greater<ll>>
  • char是有符号数，范围为-128~+127，'a'=97,'z'=122。所以小心溢出。
  • 结果取模的题目，不要用除法！不要用除法！不要用除法！而是去算逆元。比如$n\leq 10^9$这种，然后要算前$n$个数的平方和，即$1^2+2^2+...+n^2$这种，当然知道答案是$\frac{n(n+1)(2n+1)}{6}$，但是不要想着去除以6。一方面，如果先算三个数的乘积，爆long long是很正常但是我们又不想看见的结局；另一方面，你也许猜到了可以$n(n+1)/2*(2n+1)/3$，这可以保证每次必然是整除的。但为了防止爆long long，我们依然会除一次就mod一次，但是，在进行模运算后，原来是3的倍数这一性质就被抹除了，导致答案错误。所以，去算$n*(n+1)*(2n+1)*inv(6)$，然后记得乘一次就模一次。
  • 对于区间处理（比如最长/最短相同序列）（e.x. 1 1 2 1 1 1最长相同的长度是3）你在维护cnt的时候，最后那个1 1 1那一块会没有更新到（只更新了cnt但没有更新ans），在循环外要再多手动更新一次。
  • 写while语句时，记得边界检查（&&p<=n这种）（我觉得是for循环写多了导致写while老是忘边界）
  • 如此看来，还是应当在程序执行之前就做好归零/清空的准备。因为当你写出稀奇古怪的返回时刻的时候，可能你的急于return导致了有些时候，归零/清空/善后并没有做好。然后导致问题出错。
  • 取模的题记得每行的末尾都加mod，每次乘完也加mod。
  • 为结构体排序，为第一维排好序后，还是要考虑当第一维相同时，第二维的有序情况。
  • 出现爆long long的情况却又分析不出原因时，考虑是不是哪里指数爆炸了。

sol.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using PII = pair<int, int>;
template <typename T> using fc = function<T>;
using Graph = vector<vector<int>>;
#define pb push_back
#define debug(c) cerr << #c << " = " << c << endl;
#define rg(x) x.begin(), x.end()
#define rep(a, b, c) for (auto a = (b); (a) < (c); a++)
#define repe(a, b, c) for (auto a = (b); (a) <= (c); a++)
#define endl '\n'
const int MOD = 998244353;
const int N = 0;
#ifdef ONLINE_JUDGE
#define cerr assert(false);
#endif

void solve()
{
    
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
        solve();

    return 0;
}

Hash for STL

std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = vec.size();
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

三分

double cal()
{
    double l = 0, r = 1e10;
    for (int i = 1; i <= 100; i++)
    {
        double m1 = l + (r - l) / 3;
        double m2 = (r - l) / 3 * 2 + l;
        if (f(m1) < f(m2))
            l = m1;
        else
            r = m2;
    } // 求最大值
    return f(l);
}

int cal()
{
    int l = 0, r = 1e10;
    while (l + 2 < r)
    {
        int m1 = l + (r - l) / 3;
        int m2 = (r - l) / 3 * 2 + l;
        if (f(m1) < f(m2))
        {
            l = m1;
        }
        else
        {
            r = m2;
        }
    }
    int ans = f(l);
    for (int i = l + 1; i <= r; i++)
    {
        ans = max(ans, f(i));
    }
}

__int128 读写

using i128 = __int128;
i128 read()
{
    i128 x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch) && ch != '-')
        ch = getchar();
    if (ch == '-')
        f = -1, ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    return f * x;
}
void print(i128 x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}


// jiangly的板子
ostream &operator<<(ostream &os, i128 n)
{
    if (n == 0)
        return os << 0;
    string s;
    while (n > 0)
    {
        s += char('0' + n % 10);
        n /= 10;
    }
    reverse(s.begin(), s.end());
    return os << s;
}

i128 toi128(const string &s)
{
    i128 n = 0;
    for (auto c : s)
        n = n * 10 + (c - '0');
    return n;
}

i128 sqrti128(i128 n)
{
    i128 lo = 0, hi = 1E16;
    while (lo < hi)
    {
        i128 x = (lo + hi + 1) / 2;
        if (x * x <= n)
            lo = x;
        else
            hi = x - 1;
    }
    return lo;
}