From 9d3c8c0e6e1a7ba43bf3dc19350d1dca68b657a3 Mon Sep 17 00:00:00 2001 From: Chris Xiong Date: Sun, 10 Feb 2019 11:16:07 +0800 Subject: Initial commit. --- sduacm2017/index.html | 50 +++++ sduacm2017/junior/problems_j.pdf | Bin 0 -> 957171 bytes sduacm2017/junior/ranklist | 249 ++++++++++++++++++++++ sduacm2017/lec1/lec.pdf | Bin 0 -> 1393291 bytes sduacm2017/lec1/lec.tex | 440 +++++++++++++++++++++++++++++++++++++++ sduacm2017/lec1/zz.png | Bin 0 -> 3638 bytes sduacm2017/lec1/zz1.png | Bin 0 -> 9919 bytes sduacm2017/lec1/zz2.png | Bin 0 -> 864349 bytes sduacm2017/lec2/lec.pdf | Bin 0 -> 781277 bytes sduacm2017/lec2/lec.tex | 312 +++++++++++++++++++++++++++ sduacm2017/lec2/zz1.png | Bin 0 -> 9919 bytes sduacm2017/lec2/zz2.png | Bin 0 -> 353804 bytes sduacm2017/lec3/c1.png | Bin 0 -> 214300 bytes sduacm2017/lec3/c2.png | Bin 0 -> 296127 bytes sduacm2017/lec3/lec.pdf | Bin 0 -> 817559 bytes sduacm2017/lec3/lec.tex | 241 +++++++++++++++++++++ sduacm2017/senior/problems_s.pdf | Bin 0 -> 1024819 bytes sduacm2017/senior/ranklist.html | 324 ++++++++++++++++++++++++++++ 18 files changed, 1616 insertions(+) create mode 100644 sduacm2017/index.html create mode 100644 sduacm2017/junior/problems_j.pdf create mode 100644 sduacm2017/junior/ranklist create mode 100644 sduacm2017/lec1/lec.pdf create mode 100644 sduacm2017/lec1/lec.tex create mode 100644 sduacm2017/lec1/zz.png create mode 100644 sduacm2017/lec1/zz1.png create mode 100644 sduacm2017/lec1/zz2.png create mode 100644 sduacm2017/lec2/lec.pdf create mode 100644 sduacm2017/lec2/lec.tex create mode 100644 sduacm2017/lec2/zz1.png create mode 100644 sduacm2017/lec2/zz2.png create mode 100644 sduacm2017/lec3/c1.png create mode 100644 sduacm2017/lec3/c2.png create mode 100644 sduacm2017/lec3/lec.pdf create mode 100644 sduacm2017/lec3/lec.tex create mode 100644 sduacm2017/senior/problems_s.pdf create mode 100644 sduacm2017/senior/ranklist.html (limited to 'sduacm2017') diff --git a/sduacm2017/index.html b/sduacm2017/index.html new file mode 100644 index 0000000..0c41ad8 --- /dev/null +++ b/sduacm2017/index.html @@ -0,0 +1,50 @@ + + + + +11th SDU ACM/ICPC Contest + + + + + + + + + + + + + + +
+ 11th SDU ACM/ICPC Contest @ SDU & chrisoft.org +

+

General Info

+ Rules & Registeration info
+ more info(insert "20" before "17")
+

+

Junior Division

+ Ranklist
+ Problem set +

+ We are sorry about the erroneous statement of problem I. +

+

+ The test data for problem G is weaker than what it should be. + All but one accepted solution submited during the countest should actually get TLE. + The rejudge, however, would not be reflected in the final result. +

+

+ Again, we are terribly sorry for the confusion and inconvenience. +

+

+

Senior Division

+ Ranklist
+ Problem set +

+ The statement of problem F has been updated. We are sorry for the inconvenience. +

+
Copyright Chrisoft 2017  About  Site Map
+ + diff --git a/sduacm2017/junior/problems_j.pdf b/sduacm2017/junior/problems_j.pdf new file mode 100644 index 0000000..961a342 Binary files /dev/null and b/sduacm2017/junior/problems_j.pdf differ diff --git a/sduacm2017/junior/ranklist b/sduacm2017/junior/ranklist new file mode 100644 index 0000000..7acd8ab --- /dev/null +++ b/sduacm2017/junior/ranklist @@ -0,0 +1,249 @@ + + + +11th SDU ACM/ICPC Contest Junior Division + + + + + + + + +
+

11th SDU ACM/ICPC Contest Junior Division

+未签到的队伍未在此榜单中显示。 +
+
+
+ +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
RankNameSolvedTime    A        B        C        D        E        F        G        H        I        J    Total att/solv
1team5-我的青春acm物语果然有问题98781/641/1961/323/1201/352/521/2252/841/--1/1014/9
2team1-粉粉哒小裙子910391/844/2751/111/1431/1181/281/2451/880/--1/712/9
3team28-我说我帅你说队914201/863/2761/742/1531/2391/1041/2011/1740/--1/5312/9
4team2-我的貂蝉在哪里87621/940/--1/371/1371/962/481/2531/560/--1/219/8
5team4-菜811401/326/--1/383/2721/2015/1032/2471/1220/--1/521/8
6team3-能做对一个题算我输76932/220/--1/366/--1/1701/524/2371/1280/--2/818/7
7team25-咱们狠鰜沀79571/800/--1/953/2651/842/1240/--2/1920/--2/3712/7
8team9-WaterOneWater66301/340/--1/442/--1/2523/891/--2/1170/--1/5412/6
9team19-正常队名-c610401/2650/--1/592/--1/2274/1250/--7/2870/--1/1717/6
10team34-正常队名-a56742/1160/--1/765/--0/--2/950/--4/2370/--1/7015/5
11team16-专业划水59647/2530/--2/530/--0/--1/1770/--1/2820/--1/5912/5
12team6^卖女孩的小火柴40(677)7/2730/--3/601/--0/--1/1690/--1/--0/--2/1515/4
13team29-只会喊66643941/1060/--1/480/--0/--2/1920/--2/--0/--1/287/4
14team31-贾神说的队44292/2230/--1/500/--1/--1/852/--4/--0/--1/5112/4
15team7-想不出队名我也很绝望啊44421/2360/--1/--1/851/--1/1143/--0/--0/--1/79/4
16team24-不WA算我输44473/630/--1/530/--2/--1/2770/--1/--0/--1/149/4
17team35-dalao说的都45622/2120/--1/604/--0/--1/2313/--2/--0/--1/3914/4
18team13-我说对不队45821/2230/--3/1570/--0/--1/1920/--0/--0/--1/106/4
19team14-这锅我不背32762/1660/--1/760/--0/--1/--0/--0/--0/--1/145/3
20team26^嗨氏老婆后援队20(236)0/--0/--0/--1/--2/1972/--0/--0/--0/--1/196/2
21team10-取名真难队21980/--0/--4/--0/--0/--1/1650/--0/--0/--1/336/2
22team17-怎么做都不队22920/--0/--3/--1/--1/1741/--2/--0/--0/--1/1189/2
23team18-炸蛙23430/--0/--0/--0/--0/--1/2734/--0/--0/--2/707/2
24team30^混水摸鱼队10(97)4/--0/--6/--0/--0/--0/--0/--0/--0/--1/9711/1
25team32-吃饺子队1131/--0/--0/--0/--0/--3/--0/--1/--0/--1/136/1
26team27-皮皮虾我们走1190/--0/--0/--0/--0/--6/--3/--0/--0/--1/1910/1
27team15-六条腿1340/--0/--5/--0/--0/--0/--0/--0/--0/--2/347/1
28team8-一轮游～1470/--0/--6/--0/--0/--0/--0/--0/--0/--1/477/1
29team12-我就来看看11670/--0/--0/--0/--0/--3/--0/--0/--0/--5/878/1
30team33-三个水枪手116713/--0/--0/--0/--0/--0/--0/--0/--0/--3/12716/1
Submitted/1st Yes/Total Yes56/22/1914/196/348/11/1836/85/716/35/1150/28/2028/201/634/56/111/--/042/5/31325/126
+
+
+PC^2 Homepage +
+ CSS by Tomas Cerny and Ray Holder + +Created by CSUS PC^2 version 9.3.3 20160914 build 3454
+Last updated +Sat Mar 25 17:18:57 CST 2017
+ + diff --git a/sduacm2017/lec1/lec.pdf b/sduacm2017/lec1/lec.pdf new file mode 100644 index 0000000..1e79812 Binary files /dev/null and b/sduacm2017/lec1/lec.pdf differ diff --git a/sduacm2017/lec1/lec.tex b/sduacm2017/lec1/lec.tex new file mode 100644 index 0000000..af1f66d --- /dev/null +++ b/sduacm2017/lec1/lec.tex @@ -0,0 +1,440 @@ +\documentclass[aspectratio=169,hyperref={pdfencoding=auto,psdextra}]{beamer} +\usepackage[utf8]{inputenc} +\usepackage{CJKutf8} +\usepackage{ulem} +\usepackage{graphicx} +\usepackage{fancyvrb} +\usetheme{Malmoe} +\usecolortheme{default} +\begin{CJK*}{UTF8}{gbsn} +\title{「知道错了没」} +\subtitle{——如何让队友认错} +\author{Chris Xiong} +\date{2017-07-21} +\begin{document} + \frame{\titlepage} + \begin{frame} + \frametitle{「知道错了没」} + \framesubtitle{Outline} + \begin{itemize} + \item 采访 + \item dp: d(ui)p(ai) + \item dp: Knapsack problem + \item 如何让队友认错之如何殴打队友 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{采访} + \framesubtitle{\sout{a.k.a. 教学质量检查}} + \begin{itemize} + \item 上次课讲的内容大家都听懂了吗？\pause + \item 什么？不懂？\pause + \item 那还记得上次讲的什么吗？\pause + \item A Water Problem \pause + \item 已知$$f(x+1) = + \begin{cases} + a & x=0 + \\ + b & x=1 + \\ + f(x)+f(x-1)+sin(\frac{\pi x}{2}) & otherwise + \end{cases}$$ + 对于给定的$a,b,n$，求$f(n)$。$n\leq 10^{18}$。 + \item 给大家5分钟的思考时间。 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{采访} + \framesubtitle{怎么样，是不是不会啊？} + \begin{itemize} + \item 都怪宇宙智障。\\ + \includegraphics[scale=0.75]{zz.png}\pause + \item 提示：\pause周期！！\pause + \item 还不会的话就去找宇宙智障。\\ + \includegraphics[scale=0.75]{zz1.png} + \item （听说你想要表扬　厚颜无耻） + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{d(ui)p(ai)} + \begin{itemize} + \item WTF is duipai?\pause + \item Automated generation of test data and execution of several programs.\pause + \item And most importantly, compare their results.\pause + \item \sout{A nice way to waste time if you are stuck.} + \end{itemize} + \end{frame} + \begin{frame}[fragile] + \frametitle{A sample script for UNIX-like OS} + \begin{Verbatim} +#!/bin/bash +i=0 +while(true) +do + ./170312cgen > test.in + ./170312ca < test.in > aa.out + ./170312cb < test.in > bb.out + diff aa.out bb.out + if [ $? -ne 0 ] + then + break + fi + echo $i passed + let i++ +done + \end{Verbatim} +\end{frame} + \begin{frame}[fragile] + \frametitle{How to use it?} + \begin{itemize} + \item Modify the script to your needs. + \item Save it as a script, e.g.: "xxx.sh". + \item Give it the permission to execute. + Run \verb|chmod +x | in a terminal. + \item Run it! + Type \verb|./| in a terminal. + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{What does this script do?} + \begin{itemize} + \item Run the input generator. + \item Feed the generated input to the compared program A and gather results from it. + \item Do the same thing with program B. + \item Check the output. If they differ, terminate the script. Otherwise loop. + \end{itemize} + \end{frame} + \begin{frame}[fragile] + \frametitle{Explanation} + \begin{itemize} + \item + \begin{verbatim} + while(true) + do + done + break + \end{verbatim} + \item + \begin{verbatim} + > < + \end{verbatim} + redirection + \item + \begin{verbatim} + if + then + fi + $? + [, -ne + \end{verbatim} + \item Verification: \verb|diff| / custom program + \end{itemize} + \end{frame} + \begin{frame}[fragile] + \frametitle{Alternative approaches} + \begin{itemize} + \item Write a \verb|C/C++| program instead of a shell script? + \item \verb|system()| in \verb|stdlib.h| (\verb|cstdlib|) + \item return value of \verb|system()| + \item Windows batch file: + \begin{itemize} + \item \verb|IF %ERRORLEVEL% EQU 0(GOTO :loop)| + \end{itemize} + \item \sout{Powershell}? + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Writing input generators} + \begin{itemize} + \item Random? + \item Constructed special cases? + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Knapsack problem} + \framesubtitle{I suck at this} + \begin{itemize} + \item Unbounded knapsack problem + \item Bounded knapsack problem + \begin{itemize} + \item 0/1 knapsack problem + \end{itemize} + \item NP-complete! + \item A No-Dynamic-Programming-At-All variant + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Knapsack problem} + \framesubtitle{The No-DP-At-All variant} + Fractional knapsack problem (a.k.a. Continuous knapsack problem) + \begin{itemize} + \item A knapsack of capacity $W$. + \item $N$ items, each having its weight $w_i$ and value per unit weight $v_i$. + \item Select an amount $x_i$ of each item so that + the total weight doesn't exceed the capacity ( + $\displaystyle\sum_{i}^{}x_i\leq W$ + ) and maximizing the total value + $\displaystyle\sum_{i}^{}x_i \times v_i$, where $x_i \in \mathbb{R}, x_i \geq 0$. + \pause + \item Greedy. + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Knapsack problem} + \framesubtitle{0/1 knapsack problem} + \begin{itemize} + \item Still a knapsack of capacity $W$. + \item Still $N$ items, each having its weight $w_i$ + and value $v_i$. + \item For each item, determine whether to put it in + the knapsack so that the total weight doesn't + exceed the capacity and the total value is maximum. + \end{itemize} + \end{frame} + \begin{frame}[fragile] + \frametitle{Knapsack problem} + \framesubtitle{0/1 knapsack problem} + A brute-force solution: + \begin{Verbatim} +def dfs(i,remaining_capacity): + if(i==0): return 0; + if(remaining_capacity<0): + return -inf; + r1=dfs(i-1,remaining_capacity); + r2=dfs(i-1,remaining_capacity-w[i])+v[i]; + return max(r1,r2); + \end{Verbatim} + \begin{itemize} + \item Call dfs(N,W) for answer. + \item Each non-trivial invocation of dfs branch into two paths. + \item Time complexity: $O(2^N)$. + \item A minor optimization: replace the second condition + statement with +\verb|if(remaining_capacity=w[i] else 0); + \end{Verbatim} +\end{frame} + \begin{frame} + \frametitle{Knapsack problem} + \framesubtitle{0/1 knapsack problem} + \begin{itemize} + \item Recall that in the memoization version, in order to calculate results for $f[i,remaining\_capacity]$ + we must already have at least two results for $f[i-1,x]$. + \item Why don't we calculate all $f[i-1,x]$ before calculating $f[i,x]$? + \pause + \item Got the maximum value now! Want the list of selected items? + \pause + \item Traceback. + \end{itemize} + \end{frame} + \begin{frame}[fragile] + \frametitle{Knapsack problem} + \framesubtitle{0/1 knapsack problem} + \begin{itemize} + \item When we are at $i=x$ of the outer loop, all values in $f[y],y'9') + ch=getchar(); + do + { + ret=ret*10+ch-'0'; + ch=getchar(); + }while(ch>='0'&&ch<='9'); + return ret; + } + \end{Verbatim} +\end{frame} + \begin{frame}[fragile] + \frametitle{Faster I/O} + \framesubtitle{Even faster input - fread()} + \begin{Verbatim} + char s[SOME_LARGE_VALUE]; + size_t ptr,len; + len=fread(s,1,SOME_LARGE_VALUE,stdin); + int readint() + { + //replace getchar() with s[ptr++] + ... + } + \end{Verbatim} + \pause + Reading real numbers? +\end{frame} + \begin{frame}[fragile] + \frametitle{Faster I/O} + \framesubtitle{Faster output} + \begin{itemize} + \item Print digit by digit + \item Save to buffer then \verb|fwrite()| to \verb|stdout|. + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{C++11 / 14 - Useful features that reduces coding efforts} + \framesubtitle{C++11} + \begin{itemize} + \item Uniform initialization + \begin{Verbatim} + struct S{int a;double b;char c;}; + S s{1,2.0,'3'};//s.a==1; s.b==2.0; s.c=='3'; + \end{Verbatim} + \item Type inference + \begin{Verbatim} + std::set s; + auto a=1; + auto it=s.begin(); + \end{Verbatim} + \item Range-based for loop + \begin{Verbatim} + std::vector v; + for(auto &i:v)... + \end{Verbatim} + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{C++11 / 14 - Useful features that reduces coding efforts} + \framesubtitle{C++11 cont'd} + \begin{itemize} + \item Lambda functions + \begin{Verbatim} +std::sort(p+1,p+nv,[o=p[0]](const v3d& a,const v3d& b)->bool + { + double cross=(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y); + if(sgn(cross))return sgn(cross)>0; + double la=hypot(a.x-o.x,a.y-o.y); + double lb=hypot(b.x-o.x,b.y-o.y); + return la> v; + \end{Verbatim} + \item \verb|long long int|\\ + Yeah, it was not standard until C++11 (C99). + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{C++11 / 14 - Useful features that reduces coding efforts} + \framesubtitle{C++11 STL} + \begin{itemize} + \item Hash tables\\ + \verb|std::unordered_map, std::unordered_set| + \item \verb|std::tuple| + \item Regular expressions + \item Threading + \item Random number generators + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{C++11 / 14 - Useful features that reduces coding efforts} + \framesubtitle{C++14} + C++14 is a small extension to C++11. + \begin{itemize} + \item Improved \verb|auto| + \begin{Verbatim} + auto factorial(int x){ + if(x==1)return 1; + return x*factorial(x-1); + } + \end{Verbatim} + \item Improved lambda functions + \begin{Verbatim} + auto lambda=[](auto x,auto y){return x+y;}; + \end{Verbatim} + \item Lambda capture expressions + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{Common pitfalls} + \begin{itemize} + \item Huge global variable causes linkage error. + \begin{Verbatim} +int a[1LL<<12][1LL<<48],b[1LL<<12][1LL<<48],c[1LL<<12][1LL<<48]; +int main(){c[0][0]=1;} + \end{Verbatim} + Compilation result: + \begin{Verbatim} +g++ -Wall -std=c++14 -g -o "test" "test.cpp" -lm (in directory: +/home/chrisoft/code) +/tmp/ccOkFQ7A.o: In function `main': +/home/chrisoft/code/test.cpp:2:(.text+0x6): +relocation truncated to fit: R_X86_64_PC32 against symbol +`c' defined in .bss section in /tmp/ccOkFQ7A.o +collect2: error: ld returned 1 exit status +Compilation failed. + + \end{Verbatim} + \item relocation of \verb|.bss| section exceeding platform limitations. + \end{itemize} +\end{frame} + \begin{frame}[fragile] + \frametitle{Common pitfalls} + \begin{itemize} + \item Stack size is very small compared to heap + \begin{Verbatim} +int main(){int a[100000000];...} + \end{Verbatim} + \item Results in stack overflow. + \item Math library + \item \verb|memset()| TLE + \end{itemize} +\end{frame} + \begin{frame} + \frametitle{Bitmask} + \begin{itemize} + \item A set in its binary form + \item Codeforces 550B\pause + \item Codeforces 579A + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Bitmask+dp} + \begin{itemize} + \item Concept of a \textbf{state}\pause + \item Value function\pause + \item Initial state + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Bitmask+dp} + \begin{itemize} + \item TSP(Travelling Salesman Problem) + \item Given a list of cities and the distances between each pair of cities, + what is the shortest possible route that visits each city exactly once and + returns to the origin city?\pause + \item f[s][i]: s: set of visited cites, i: current city + \item functional equation: + $ + f[s][i]= + \displaystyle \min_{k:N}f[s-{i}][k]+dist[k][i] (k\notin s) + $ + \item Initial state: f[U][0]=0;\pause + \item Variant\pause + \item Loop direction + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Bitmask+dp} + \begin{itemize} + \item TSP: POJ 3311 + \item Counting: POJ 3254 + \item f[i][s]: row i with set s occupied + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{如何让队友认错之如何表扬队友} + \framesubtitle{队友需要表扬才能更有生产力} + \includegraphics[scale=0.75]{zz1.png} + \end{frame} + \begin{frame} + \frametitle{如何让队友认错之如何表扬队友} + \framesubtitle{光辉事迹} + \begin{itemize} + \item 比赛中要其他队伍帮忙写对拍 + \item 比赛中睡3小时觉 + \item 全权负责实验室事务 + \item 发说说 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{宇宙智障的说说} + + \begin{multicols}{2} + 就终于考完试了\_(:зゝ∠)\_\\ + 然而暑假这种？不存在的(滑稽\\ + 还是献给辣鸡的(划掉)acm好了\\ + 学期结束,事儿反而就又突然多了起来\\ + 假装已有计划的专题训练\\ + 各种姿势被虐的多校联合\\ + 以及暑期集训的萌新教学\\ + 与开始正式接手的实验室各种大小事务的锅\\ + 相信,一定会是个忙碌的七八月份吧\\ + 希望,也同会是个充满收获的七八月\\ + 就也会更期待着\\ + 在八月初的短假里\\ + 与小姐姐愉快的玩耍呢\\ + 总之,一定会是个不平凡的假期\\ + 再以及,小姐姐寄的明信片也终于到了:)\\ + \end{multicols} + \end{frame} + + \begin{frame} + \frametitle{宇宙智障的说说} + \includegraphics[scale=0.5]{zz2.png} + \end{frame} + \begin{frame} + \frametitle{为何要表扬队友} + \begin{itemize} + \item 让恬不知耻的队友知道错（似乎对宇宙智障无效） + \item 叫醒队友 + \item \sout{鼓励}队友\sout{WA更多题} + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{放假事宜} + \begin{itemize} + \item 宇宙智障已经畏罪潜逃 + \item 宇宙智障8月7日将被扭送 + \item 大家一定不用比宇宙智障回来的早 + \end{itemize} + \end{frame} +\end{CJK*} +\end{document} + diff --git a/sduacm2017/lec2/zz1.png b/sduacm2017/lec2/zz1.png new file mode 100644 index 0000000..8e5bcf8 Binary files /dev/null and b/sduacm2017/lec2/zz1.png differ diff --git a/sduacm2017/lec2/zz2.png b/sduacm2017/lec2/zz2.png new file mode 100644 index 0000000..ce8d970 Binary files /dev/null and b/sduacm2017/lec2/zz2.png differ diff --git a/sduacm2017/lec3/c1.png b/sduacm2017/lec3/c1.png new file mode 100644 index 0000000..0e6b37c Binary files /dev/null and b/sduacm2017/lec3/c1.png differ diff --git a/sduacm2017/lec3/c2.png b/sduacm2017/lec3/c2.png new file mode 100644 index 0000000..93c15f3 Binary files /dev/null and b/sduacm2017/lec3/c2.png differ diff --git a/sduacm2017/lec3/lec.pdf b/sduacm2017/lec3/lec.pdf new file mode 100644 index 0000000..8eb6176 Binary files /dev/null and b/sduacm2017/lec3/lec.pdf differ diff --git a/sduacm2017/lec3/lec.tex b/sduacm2017/lec3/lec.tex new file mode 100644 index 0000000..990c6e5 --- /dev/null +++ b/sduacm2017/lec3/lec.tex @@ -0,0 +1,241 @@ +\documentclass[aspectratio=169,hyperref={pdfencoding=auto,psdextra}]{beamer} +\usepackage[utf8]{inputenc} +\usepackage{CJKutf8} +\usepackage{ulem} +\usepackage{graphicx} +\usepackage{fancyvrb} +\usepackage{amsmath} +\usepackage{multicol} +\usetheme{Malmoe} +\usecolortheme{default} +\begin{CJK*}{UTF8}{gbsn} +\title{「初中数学都不会」} +\subtitle{——Computational Geometrics} +\author{Chris Xiong} +\date{2017-08-18} +\begin{document} + \frame{\titlepage} + \begin{frame} + \frametitle{「初中数学都不会」} + \framesubtitle{Outline} + \begin{itemize} + \item Basics + \begin{itemize} + \item Vectors + \item Distances + \item Area + \item Intersections + \item Transformations + \end{itemize} + \item Convex hull + \item Extra fun + \item Templates + \item 殴打宇宙智障 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Basics} + \framesubtitle{Vectors} + \begin{itemize} + \item Computational Gemoetrics in ICPC=\\ + \hspace{1cm}40\% Junior high school maths+\\ + \hspace{1cm}30\% Senior high school maths+\\ + \hspace{1cm}20\% Brainstorming+\\ + \hspace{1cm}10\% College maths + \item $\mathbf{u}$, $\mathbf{v}$, $\vec{u}$, $\vec{v}$ + \item $\vec{u}+\vec{v}$,$\vec{u}-\vec{v}$,$s\vec{u}$,$\vec{u}\cdot\vec{v}$,$\vec{u}\times\vec{v}$ + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Basics} + \framesubtitle{Distances} + \begin{itemize} + \item point 2 point + \item point 2 line + \pause + \item polygon 2 polygon??? + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Basics} + \framesubtitle{Area} + \begin{itemize} + \item Circle??? + \item Triangle? + \begin{itemize} + \item \sout{$ah/2$} + \item Heron's formula + \item Cross product + \end{itemize} + \item Polygon??? + \begin{itemize} + \item Slicing + \end{itemize} + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Basics} + \framesubtitle{Intersections} + \begin{itemize} + \item point \& line + \item point \& segment + \item line \& line + \item line \& segment + \item segment \& segment + \item circle \& line + \item circle \& circle + \pause + \item \sout{convex} polygon \& point \pause + \begin{itemize} + \item \sout{randomizing} (polyhedron) + \item ray casting + \item winding number + \end{itemize} + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Basics} + \framesubtitle{Transformations} + \begin{itemize} + \item Scaling + \item Rotation + \item ${\displaystyle {\begin{bmatrix}s_x&0\\0&s_y\end{bmatrix}}}$ + \item ${\displaystyle {{\begin{bmatrix}\cos \theta &\sin \theta \\-\sin \theta &\cos \theta \end{bmatrix}}}}$ + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Convex hull} + \framesubtitle{WTF???} + \begin{itemize} + \item Smallest convex polygon (set) that contains a set of points. + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Convex hull} + \framesubtitle{Algorithms} + \begin{itemize} + \item Brute force: gift wrapping + \item Graham scan + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Convex hull} + \framesubtitle{Gift wrapping} + \begin{itemize} + \item The left most point must be in the resulting set + \item Starting from that point, select the next point such that + all points are \textbf{to the right} of the newly formed line. + \item Time complexity: $O(nh)$ + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Convex hull} + \framesubtitle{Graham scan} + \begin{itemize} + \item Find an extreme point and sort the remaining point according + to polar angle. + \item Start with a stack with two items, the extreme point and the + first point in the sorted list. + \item ($P_0$ denotes the top element of the stack, $P_1$ denotes the + element under $P_0$) For each point left in the list ($T$), pop the + stack until $\overrightarrow{P_1P_0}$ and $\overrightarrow{P_0T}$ forms + \textbf{a left turn}. Then push $T$ onto the stack. + \item Time complexity: $O(n log n)$ (with sorting) + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Convex hull} + \framesubtitle{Example: NEERC 08 A} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Example: PetrSU SC 04 C} + Arc-arc intersection + \includegraphics[scale=0.5]{c1.png} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Example: PetrSU SC 04 C} + \includegraphics[scale=0.36]{c2.png} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Example: MultiUniversity Traning 20170815 H} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Example: Asia GuangzhouRC 14 H} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Example: "Angry birds"} + One of the few problems of computational geometrics in ICPC + that involves college maths. + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{CG. Combined with other algorithms} + \end{frame} + \begin{frame} + \frametitle{Extra fun} + \framesubtitle{Rotating calipers} + Solves: + \begin{itemize} + \item Max/min width of convex polygon + \item Max/min distance between two convex polygons + \item Antipodal points/Farthest pairs + \item Union/intersection of convex polygons + \item Min area/perimeter obb + \item etc. + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{Templates} + \framesubtitle{Critical for Computational Geometrics (maybe)} + \begin{itemize} + \item Basic operations + \item Basic intersections + \item Circle-line intersection + \item Circle-triangle intersection + \item Circle-circle intersection + \item 3D vector operations + \item Half-plane intersection + \item Cloest/Farthest Pair + \item etc. + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{殴打宇宙智障} + \framesubtitle{光辉事迹+1} + \begin{itemize} + \item 建完图后把图清空然后跑网络流\pause + \item 熟悉你的模板\pause + \item 多校睡觉\pause + \item 队伍组成 + \item 代码手？\pause + \item 违反中央八项规定\pause + \item 口技 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{殴打宇宙智障} + \framesubtitle{后事} + \begin{itemize} + \item 21日最后一次讲课 + \item 8月31日计科退宿舍 + \item 如有不同以宇宙智障为准 + \end{itemize} + \end{frame} + \begin{frame} + \frametitle{殴打宇宙智障} + \framesubtitle{没来得及讲的东西} + \begin{itemize} + \item 概率（解方程/dp）、高斯消元 + \item 网络流 + \item 好像没什么了？ + \item Good luck to ya. + \end{itemize} + \end{frame} +\end{CJK*} +\end{document} + diff --git a/sduacm2017/senior/problems_s.pdf b/sduacm2017/senior/problems_s.pdf new file mode 100644 index 0000000..f7839b5 Binary files /dev/null and b/sduacm2017/senior/problems_s.pdf differ diff --git a/sduacm2017/senior/ranklist.html b/sduacm2017/senior/ranklist.html new file mode 100644 index 0000000..7230ff5 --- /dev/null +++ b/sduacm2017/senior/ranklist.html @@ -0,0 +1,324 @@ + + + +11th SDU ACM/ICPC Contest Senior Division + + + + + + + + +
+

11th SDU ACM/ICPC Contest Senior Division

+

+
+
+ +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
RankNameSolvedTime    A        B        C        D        E        F        G        H        I        J    Total att/solv
+
A
+		 +
B
+		 +
C
+		 +
D
+		 +
E
+		 +
F
+		 +
G
+		 +
H
+		 +
I
+		 +
J
+
*team1 - 粉粉哒小裙子*77233/921/--1/1461/1162/361/--4/--1/123/2041/1718/7
1team28 - Deadline!78183/970/--1/1231/1851/600/--3/--1/112/2272/3514/7
2team16 - 不要脸了还79103/1640/--1/1541/1752/670/--0/--1/101/2481/3210/7
3team39 - 水水题65153/431/--1/921/1503/720/--0/--1/33/--4/1517/6
4team24 - 正常队名65882/250/--3/1943/1792/583/--0/--1/200/--1/3215/6
5team15 - creating66226/460/--4/1562/1702/556/--3/--1/150/--2/4026/6
*team6 - 我说我帅你说队*67043/2130/--1/903/2191/320/--0/--2/133/--1/3714/6
6team13 - 很难受67752/791/--4/1072/2503/2010/--0/--1/80/--1/5014/6
7team45 - ShaBiLLX68121/983/--2/1443/2754/1580/--0/--1/200/--1/1715/6
8team33 - 在座的都是大佬69357/1190/--1/1841/2753/1330/--0/--1/313/--3/5319/6
9team38 - 你得是匹狼69408/2670/--1/1162/2461/660/--0/--1/150/--2/5015/6
10team22 - wa610083/1530/--1/2364/2753/1140/--0/--2/150/--3/5516/6
11team40 - 宫保鸡丁队610341/1950/--4/1483/2492/1650/--0/--1/260/--3/15114/6
12team31 - 你随便取个吧610612/1560/--14/2061/2964/610/--0/--1/150/--3/2725/6
13team44 - 小白菜6123327/2825/--1/1411/1791/640/--0/--1/145/--6/1347/6
14team9 - helloworld6134511/2203/--11/1752/2705/870/--0/--2/201/--1/17336/6
15team2 - 一起抱大腿52873/580/--1/1246/--1/104/--0/--1/34/--2/3222/5
*team4 - 咱们狠鰜沀*53448/--1/--1/1451/763/460/--0/--1/200/--2/1717/5
16team42 - meat54821/1840/--3/1120/--1/660/--0/--1/150/--3/459/5
17team25 - 15份的树莓派56571/1730/--1/1770/--1/940/--0/--1/180/--3/1557/5
18team14 - [此处是很厉害的队名]588828/--0/--8/1505/2873/1030/--0/--2/490/--2/5948/5
19team30 - 此刻尽丝滑589411/2720/--5/2120/--2/1200/--0/--3/380/--4/9225/5
20team41 - ACM593614/2290/--10/2441/--2/1230/--0/--2/450/--1/3530/5
21team23 - 122@^40(704)6/--0/--2/2420/--6/1250/--0/--5/150/--2/10221/4
21team50 - 开开心心写代码^40(793)0/--3/--7/--1/2763/1720/--0/--5/430/--3/14222/4
21team18 - 123^40(1049)8/2610/--5/1650/--3/2760/--0/--4/470/--14/--34/4
24team19 - 这个队名很正常44096/2000/--0/--0/--1/660/--0/--1/260/--1/579/4
25team49 - 干蒸烧卖糯米鸡44250/--0/--1/1390/--2/870/--0/--1/182/--2/1618/4
26team48 - 小队44922/1600/--10/--0/--4/1680/--0/--1/220/--2/6219/4
27team26 - 算计啊44934/--0/--1/1620/--5/1860/--0/--1/210/--1/4412/4
28team36 - 胡德平呀胡德平45973/--0/--1/1491/--2/850/--0/--3/400/--5/18315/4
29team32 - 得奖？不存在的！46687/--0/--5/2250/--4/1140/--0/--1/220/--2/14719/4
*team3 - 不WA算我输*483610/2900/--9/2399/--3/--0/--0/--1/150/--3/1235/4
30team20 - ZING49484/2512/--0/--0/--12/2810/--0/--1/240/--4/5223/4
31team47 - 水一水410348/2860/--9/--0/--2/1760/--0/--1/150/--8/27728/4
32team8 - 梅锋真没疯32685/--0/--1/1290/--2/761/--0/--1/430/--5/--15/3
33team29 - 啤酒瓶32915/--2/--6/--1/--2/350/--0/--2/50/--3/17121/3
34team5 - 午时已到333610/--0/--9/--0/--1/280/--0/--1/80/--5/24026/3
35team34 - 一颗赛艇34562/--2/--7/1950/--2/420/--0/--1/790/--10/--24/3
36team21 - 咸鱼非余34628/--0/--0/--0/--5/--0/--0/--1/73/1871/24818/3
37team46 - 伊利纯牛奶349812/2142/--0/--0/--0/--5/--0/--3/1160/--1/12823/3
38team12 - 小腿想成为大腿^20(359)4/--2/--0/--0/--3/--0/--0/--1/1190/--6/24016/2
39team35 - 风水扬沙果粒无敌必胜超级厉害队^20(512)7/--0/--10/2610/--0/--0/--0/--3/310/--0/--20/2
40team43 - triple_six21398/--0/--11/--0/--4/630/--0/--1/160/--9/--33/2
41team10 - 明月照大江21672/927/--0/--0/--0/--0/--7/--1/550/--17/--34/2
42team27 - 代码怎么写都队^10(43)5/--0/--0/--0/--7/--0/--0/--1/430/--5/--18/1
43team17 - 在废人的领域也同样无敌11810/--0/--0/--0/--0/--0/--0/--2/1610/--16/--18/1
44team11 - String Name118218/--4/--7/--0/--10/--0/--0/--5/1020/--0/--44/1
Submitted/1st Yes/Total Yes295/25/2939/--/0181/90/3356/76/19135/10/3920/--/017/--/078/3/4830/187/4177/12/391028/211
+
+
+PC^2 Homepage +
+ CSS by Tomas Cerny and Ray Holder + +Created by CSUS PC^2 version 9.3.3 20160914 build 3454
+Last updated +Sat Apr 08 17:40:05 CST 2017
+ + -- cgit v1.2.3