头像

Wegoon




离线:18小时前


最近来访(54)
用户头像
Liuyz.
用户头像
冰冷酒
用户头像
这题太baby了
用户头像
穿着校服浪天下.
用户头像
Magic_Zq
用户头像
QQ.wgf.er
用户头像
薛定谔的大白猫
用户头像
从未看过满天繁星
用户头像
善良的大铁牛
用户头像
cdlyk
用户头像
gwj12345
用户头像
沐星不仙了
用户头像
yxc
用户头像
aezro
用户头像
1916060101
用户头像
2016070111
用户头像
澍叶
用户头像
用户头像
自律
用户头像
目至恦


Wegoon
20小时前

知识点:数学知识、线性筛法(欧拉筛法)、欧拉函数

时间复杂度:$O(n)$,线性筛法(欧拉筛法)求$1-n$这$n$个数的欧拉函数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, prime[N], cnt, ph[N];
bool st[N];
ll getEuler(int x) {
    ll ans = 0;
    ph[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if(!st[i]) {
            prime[cnt ++ ] = i;
            ph[i] = i - 1;
        }
        for (int j = 0; prime[j] <= n / i; j ++ ) {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) {
                ph[i * prime[j]] = prime[j] * ph[i];
                break;
            }
            ph[i * prime[j]] = (prime[j] - 1) * ph[i];
        }
    }
    for (int i = 1; i <= n; i ++ ) ans += ph[i];
    return ans;
}
int main () {
    cin >> n;
    cout << getEuler(n) << endl;
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

Wegoon
4天前

知识点:数学知识、欧拉函数、容斥原理

时间复杂度:$O(\sqrt[]{n})$,分解质因数求解一个数$n$的欧拉函数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a, ans;
void chuli (int x) {
    for (int i = 2; i <= x / i; i ++ ) {
        if (x % i == 0) ans = ans / i * (i - 1);
        while (x % i == 0) x /= i;
    }
    if(x > 1) ans = ans / x * (x - 1);
}
int main () {
    cin >> n;
    while (n -- ) {
        cin >> a;
        ans = a;
        chuli(a);
        cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4074. 铁路与公路

Wegoon
20天前

知识点:BFS

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int N = 5e2;
int n, m, g[N][N], a, b;
bool st[N];
int bfs(int x) {
    sizeof(st, 0, sizeof st);
    queue<P> q;
    q.push({0, 1});
    st[1] = true;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int dist = t.first, v = t.second;
        if(v == n) return dist;
        for (int i = 1; i <= n; i ++ ) {
            if(!st[i] && g[v][i] == x) {
                q.push({dist + 1, i});
                st[i] = true;
            }
        }
    }
    return 0x3f3f3f3f;
}
int main() {
    cin >> n >> m;
    while (m -- ) {
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    int ans;
    if(g[1][n]) ans = bfs(0);
    else ans = bfs(1);
    if(ans == 0x3f3f3f3f) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 4073. 找规律输出

Wegoon
20天前

知识点:模拟

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        if(i % 2) cout << "I love ";
        else cout << "I hate ";
        if (i == n - 1) cout << "it ";
        else cout << "that ";
    }
    return 0;
}



Wegoon
22天前

.vimrc

" An example for a vimrc file.
"
" To use it, copy it to
"     for Unix and OS/2:  ~/.vimrc
"             for Amiga:  s:.vimrc
"  for MS-DOS and Win32:  $VIM\_vimrc
"           for OpenVMS:  sys$login:.vimrc

" When started as "evim", evim.vim will already have done these settings.
if v:progname =~? "evim"
  finish
endif

" Use Vim settings, rather then Vi settings (much better!).
" This must be first, because it changes other options as a side effect.
set nocompatible

" allow backspacing over everything in insert mode
set backspace=indent,eol,start

if has("vms")
  set nobackup          " do not keep a backup file, use versions instead
else
  set backup            " keep a backup file
endif
set history=50          " keep 50 lines of command line history
set ruler               " show the cursor position all the time
set showcmd             " display incomplete commands
set incsearch           " do incremental searching
"==========================================================================
"My Setting-sunshanlu
"==========================================================================
vmap <leader>y :w! /tmp/vitmp<CR>
nmap <leader>p :r! cat /tmp/vitmp<CR>

"语法高亮
syntax enable
syntax on
"显示行号
set nu

"修改默认注释颜色
"hi Comment ctermfg=DarkCyan
"允许退格键删除
"set backspace=2
"启用鼠标
set mouse=a
set selection=exclusive
set selectmode=mouse,key
"按C语言格式缩进
set cindent
set autoindent
set smartindent
set shiftwidth=4

" 允许在有未保存的修改时切换缓冲区
"set hidden

" 设置无备份文件
set writebackup
set nobackup

"显示括号匹配
set showmatch
"括号匹配显示时间为1(单位是十分之一秒)
set matchtime=5
"显示当前的行号列号:
set ruler
"在状态栏显示正在输入的命令
set showcmd

set foldmethod=syntax
"默认情况下不折叠
set foldlevel=100
" 开启状态栏信息
set laststatus=2
" 命令行的高度,默认为1,这里设为2
set cmdheight=2


" 显示Tab符,使用一高亮竖线代替
set list
"set listchars=tab:\|\ ,
set listchars=tab:>-,trail:-


"侦测文件类型
filetype on
"载入文件类型插件
filetype plugin on
"为特定文件类型载入相关缩进文件
filetype indent on
" 启用自动补全
filetype plugin indent on 


"设置编码自动识别, 中文引号显示
filetype on "打开文件类型检测
"set fileencodings=euc-cn,ucs-bom,utf-8,cp936,gb2312,gb18030,gbk,big5,euc-jp,euc-kr,latin1
set fileencodings=utf-8,gb2312,gbk,gb18030
"这个用能很给劲,不管encoding是什么编码,都能将文本显示汉字
"set termencoding=gb2312
set termencoding=utf-8
"新建文件使用的编码
set fileencoding=utf-8
"set fileencoding=gb2312
"用于显示的编码,仅仅是显示
set encoding=utf-8
"set encoding=utf-8
"set encoding=euc-cn
"set encoding=gbk
"set encoding=gb2312
"set ambiwidth=double
set fileformat=unix


"设置高亮搜索
set hlsearch
"在搜索时,输入的词句的逐字符高亮
set incsearch

" 着色模式
set t_Co=256
"colorscheme wombat256mod
"colorscheme gardener
"colorscheme elflord
colorscheme desert
"colorscheme evening
"colorscheme darkblue
"colorscheme torte
"colorscheme default

" 字体 && 字号
set guifont=Monaco:h10
"set guifont=Consolas:h10

" :LoadTemplate       根据文件后缀自动加载模板
"let g:template_path='/home/ruchee/.vim/template/'

" :AuthorInfoDetect   自动添加作者、时间等信息,本质是NERD_commenter && authorinfo的结合
""let g:vimrc_author='sunshanlu'
""let g:vimrc_email='sunshanlu@baidu.com'
""let g:vimrc_homepage='http://www.sunshanlu.com'
"
"
" Ctrl + E            一步加载语法模板和作者、时间信息
""map <c-e> <ESC>:AuthorInfoDetect<CR><ESC>Gi
""imap <c-e> <ESC>:AuthorInfoDetect<CR><ESC>Gi
""vmap <c-e> <ESC>:AuthorInfoDetect<CR><ESC>Gi



" ======= 引号 && 括号自动匹配 ======= "
"
":inoremap ( ()<ESC>i

":inoremap ) <c-r>=ClosePair(')')<CR>
"
":inoremap { {}<ESC>i
"
":inoremap } <c-r>=ClosePair('}')<CR>
"
":inoremap [ []<ESC>i
"
":inoremap ] <c-r>=ClosePair(']')<CR>
"
":inoremap < <><ESC>i
"
":inoremap > <c-r>=ClosePair('>')<CR>
"
"":inoremap " ""<ESC>i
"
":inoremap ' ''<ESC>i
"
":inoremap ` ``<ESC>i
"
":inoremap * **<ESC>i

" 每行超过80个的字符用下划线标示
""au BufRead,BufNewFile *.s,*.asm,*.h,*.c,*.cpp,*.java,*.cs,*.lisp,*.el,*.erl,*.tex,*.sh,*.lua,*.pl,*.php,*.tpl,*.py,*.rb,*.erb,*.vim,*.js,*.jade,*.coffee,*.css,*.xml,*.html,*.shtml,*.xhtml Underlined /.\%81v/
"
"
" For Win32 GUI: remove 't' flag from 'guioptions': no tearoff menu entries
" let &guioptions = substitute(&guioptions, "t", "", "g")

" Don't use Ex mode, use Q for formatting
map Q gq

" This is an alternative that also works in block mode, but the deleted
" text is lost and it only works for putting the current register.
"vnoremap p "_dp

" Switch syntax highlighting on, when the terminal has colors
" Also switch on highlighting the last used search pattern.
if &t_Co > 2 || has("gui_running")
  syntax on
  set hlsearch
endif

" Only do this part when compiled with support for autocommands.
if has("autocmd")

  " Enable file type detection.
  " Use the default filetype settings, so that mail gets 'tw' set to 72,
  " 'cindent' is on in C files, etc.
  " Also load indent files, to automatically do language-dependent indenting.
  filetype plugin indent on

  " Put these in an autocmd group, so that we can delete them easily.
  augroup vimrcEx
  au!

  " For all text files set 'textwidth' to 80 characters.
  autocmd FileType text setlocal textwidth=80

  " When editing a file, always jump to the last known cursor position.
  " Don't do it when the position is invalid or when inside an event handler
  " (happens when dropping a file on gvim).
  autocmd BufReadPost *
    \ if line("'\"") > 0 && line("'\"") <= line("$") |
    \   exe "normal g`\"" |
    \ endif

  augroup END

else

  set autoindent                " always set autoindenting on

endif " has("autocmd")

" 增加标行高亮
set cursorline
hi CursorLine  cterm=NONE   ctermbg=darkred ctermfg=white

" 设置tab是四个空格
set ts=4
set expandtab

" 主要给Tlist使用
let Tlist_Exit_OnlyWindow = 1
let Tlist_Auto_Open = 1

.tmux.conf

set-option -g status-keys vi
setw -g mode-keys vi

setw -g monitor-activity on

# setw -g c0-change-trigger 10
# setw -g c0-change-interval 100

# setw -g c0-change-interval 50
# setw -g c0-change-trigger  75


set-window-option -g automatic-rename on
set-option -g set-titles on
set -g history-limit 100000

#set-window-option -g utf8 on

# set command prefix
set-option -g prefix C-a
unbind-key C-b
bind-key C-a send-prefix

bind h select-pane -L
bind j select-pane -D
bind k select-pane -U
bind l select-pane -R

bind -n M-Left select-pane -L
bind -n M-Right select-pane -R
bind -n M-Up select-pane -U
bind -n M-Down select-pane -D

bind < resize-pane -L 7
bind > resize-pane -R 7
bind - resize-pane -D 7
bind + resize-pane -U 7


bind-key -n M-l next-window
bind-key -n M-h previous-window



set -g status-interval 1
# status bar
set -g status-bg black
set -g status-fg blue


#set -g status-utf8 on
set -g status-justify centre
set -g status-bg default
set -g status-left " #[fg=green]#S@#H #[default]"
set -g status-left-length 20


# mouse support
# for tmux 2.1
# set -g mouse-utf8 on
set -g mouse on
#
# for previous version
#set -g mode-mouse on
#set -g mouse-resize-pane on
#set -g mouse-select-pane on
#set -g mouse-select-window on


#set -g status-right-length 25
set -g status-right "#[fg=green]%H:%M:%S #[fg=magenta]%a %m-%d #[default]"

# fix for tmux 1.9
bind '"' split-window -vc "#{pane_current_path}"
bind '%' split-window -hc "#{pane_current_path}"
bind 'c' new-window -c "#{pane_current_path}"

# run-shell "powerline-daemon -q"

# vim: ft=conf



Wegoon
26天前

知识点:贪心、DP

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
struct node {
    int maxn, l, r;
} dp[N], res;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    dp[0].maxn = res.maxn = -1;
    for (int i = 1; i <= n; i ++ ) {
        if(dp[i - 1].maxn >= 0 ) {
            dp[i].maxn = dp[i - 1].maxn + a[i];
            dp[i].l = dp[i - 1].l;
            dp[i].r = i;
        }else {
            dp[i].maxn = a[i];
            dp[i].l = dp[i].r = i;
        }
        if(res.maxn < dp[i].maxn) res = dp[i];
    }
    if(!res.l && !res.r) res.maxn = 0, res.l = 1, res.r = n;
    cout << res.maxn << ' ' << a[res.l] << ' ' << a[res.r] << endl;
    return 0;
}


活动打卡代码 AcWing 4002. 构造数组

Wegoon
1个月前

知识点:数学、组合计数

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3 + 5, mod = 1e9 + 7;
int n, m, c[N][N];
int main() {
    cin >> n >> m;
    int a = 2 * m + n - 1, b = n - 1;
    for (int i = 0; i <= a; i ++ ) {
        for (int j = 0; j <= i && j <= b; j ++ ) {
            if(j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
            else c[i][j] = 1;
        }
    }
    cout << c[a][b] << endl;
    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

Wegoon
1个月前

知识点:贪心

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4 + 5;
int n;
struct node {
    int w, s;
    bool operator< (const node &a)const {
        return w + s < a.w + a.s;
    }
} a[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i].w >> a[i].s;
    sort(a, a + n);
    int sum = 0, maxn = -2e9;
    for (int i = 0; i < n; i ++ ) {
        maxn = max(maxn, sum - a[i].s);
        sum += a[i].w;
    }
    cout << maxn << endl;
    return 0;
}


活动打卡代码 AcWing 104. 货仓选址

Wegoon
1个月前

知识点:排序、快速选择算法、贪心、绝对值不等式

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], res;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i]; 
    sort(a, a + n);
    for (int i = 0; i < n / 2; i ++ ) res += a[n - 1 - i] - a[i];
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

Wegoon
1个月前

知识点:贪心、排序不等式

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, a[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);
    ll res = 0;
    for (int i = 0; i < n - 1; i ++ ) res += (n - 1 - i) * a[i];
    cout << res << endl;
    return 0;
}