Codeforces Round #308 (Div. 2)
Codeforces Round #308 (Div. 2)
AB 水题
C 进制转换,挺有意思
1 #include <iostream> 2 #include <cstdio> 3 #include <fstream> 4 #include <algorithm> 5 #include <cmath> 6 #include <deque> 7 #include <vector> 8 #include <queue> 9 #include <string> 10 #include <cstring> 11 #include <map> 12 #include <stack> 13 #include <set> 14 #define LL long long 15 #define INF 0x3f3f3f3f 16 //#define OPEN_FILE 17 using namespace std; 18 vector<int> p; 19 int main() 20 { 21 #ifdef OPEN_FILE 22 freopen("in.txt", "r", stdin); 23 freopen("out.txt", "w", stdout); 24 #endif // OPEN_FILE 25 int w, m; 26 p.empty(); 27 scanf("%d%d", &w, &m); 28 bool flag; 29 while (m != 0){ 30 p.push_back(m % w); 31 m /= w; 32 } 33 flag = false; 34 for (int i = 0; i < p.size(); i++){ 35 if (p[i] == 0 || p[i] == 1){ 36 continue; 37 } 38 if (p[i] - w == -1){ 39 p[i] = -1; 40 if (p.size() - i == 1){ 41 break; 42 } 43 p[i + 1] += 1; 44 int j = i + 1; 45 while (p[j] >= w){ 46 if (p.size() - j == 1){ 47 p[j] = 0; 48 p.push_back(1); 49 break; 50 } 51 p[j] = 0; 52 p[j + 1] += 1; 53 j++; 54 } 55 } 56 else{ 57 flag = true; 58 break; 59 } 60 } 61 if (flag){ 62 printf("NO "); 63 } 64 else{ 65 printf("YES "); 66 } 67 }
D 平面中N个点,找出三点不共线的数目
1 #include <iostream> 2 #include <cstdio> 3 #include <fstream> 4 #include <algorithm> 5 #include <cmath> 6 #include <deque> 7 #include <vector> 8 #include <queue> 9 #include <string> 10 #include <cstring> 11 #include <map> 12 #include <stack> 13 #include <set> 14 #define LL long long 15 #define INF 0x3f3f3f3f 16 #define MAXM 2001 17 using namespace std; 18 int x[MAXM], y[MAXM]; 19 double a[MAXM]; 20 bool compare(double a, double b){ 21 return a < b; 22 } 23 int main() 24 { 25 int n; 26 scanf("%d", &n); 27 for (int i = 1; i <= n; i++){ 28 scanf("%d%d", &x[i], &y[i]); 29 } 30 LL ans; 31 ans = (n - 1) * (n - 2); 32 ans = ans * n / 6; 33 int m = 0; 34 for (int i = 1; i <= n; i++){ 35 m = 0; 36 for (int j = i + 1; j <= n; j++){ 37 if (x[j] == x[i]){ 38 a[++m] = INF; 39 continue; 40 } 41 double temp1 = y[j] - y[i]; 42 double temp2 = x[j] - x[i]; 43 a[++m] = temp1 / temp2; 44 if (a[m] == 1.0){ 45 a[m] = a[m]; 46 } 47 } 48 sort(a + 1, a + m + 1); 49 int t = 1; 50 for (int j = 2; j <= m; j++){ 51 if (a[j] - a[j - 1] < 1e-7){ 52 ++t; 53 continue; 54 } 55 ans -= t *(t - 1) / 2; 56 t = 1; 57 } 58 if (t != 1){ 59 ans -= t *(t - 1) / 2; 60 } 61 } 62 printf("%I64d ", ans); 63 }