Wegoon

4115

Liuyz.

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;
}


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;
}


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;
}


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
"==========================================================================

"语法高亮
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

"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个的字符用下划线标示
"
"
" 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).
\ 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;
}


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;
}


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;
}


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;
}


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;
}