信息小白刷题记
半年前，我还是个什么都不懂的小白。很久以前我就知道了编程，甚至有些向往，但却没有主动争取。而那时，我有了机会，接触了\(OI\)，我就深刻地爱上了它。我相信省一不是我奋斗的目标，我将会走的更远……
距\(NOIp2019\)还有\(83\)天
\(2019.8.7\)
\(1.\) \(P2831\)愤怒的小鸟
\(Code:\)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps = 1e-8;
const int N = 20;
int f[1 << N], e[1 << N], ln[N][N];
double x[N], y[N];
#define func(x) (x * x)
void solve(double &a, double &b, int i, int j) {
double X1 = func(x[i]),
X2 = func(x[j]);
b = (X1 * y[j] - X2 * y[i]) / (X1 * x[j] - X2 * x[i]);
a = (y[i] - b * x[i]) / X1;
}
bool check(double a, double b, int i) {
double X = func(x[i]);
return fabs(a * X + b * x[i] - y[i]) < eps;
}
int main() {
for(int i = 0; i < (1 << 18); i++) {
int j = 0;
for(; j < 18 && (i & (1 << j)); j++);
e[i] = j;
}
int T;
scanf("%d", &T);
while(T--) {
memset(ln, 0, sizeof(ln));
memset(f, 0x3f, sizeof(f));
int n, m;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%lf %lf", x + i, y + i);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(fabs(x[i] - x[j]) < eps || i == j) continue;
double a, b;
solve(a, b, i, j);
if(a > -eps) continue;
for(int k = 0; k < n; k++)
if(check(a, b, k)) ln[i][j] |= (1 << k);
}
}
f[0] = 0;
for(int i = 0; i < (1 << n); i++) {
int j = e[i], p = i | (1 << j);
f[p] = min(f[p], f[i] + 1);
for(int k = 0; k < n; k++)
f[i | ln[j][k]] =
min(f[i | ln[j][k]], f[i] + 1);
}
printf("%d\n", f[(1 << n) - 1]);
}
return 0;
}\(2.\) \(P1018\)乘积最大
本题其实就是个简单的\(DP+\)高精，但因为有高精所以难度就上了一个档次。
定义状态：\(f[i][j]\)表示前\(i\)个字符分出了\(j\)个乘号得到的最大乘积，且有\(j<i\)。
若\(a\)数组为原串，则转移方程：
\[f[i][j]=max(f[i][j],f[i][j-1]*a_{k-i}),\text{其中}k,j<i\text{且}k←j-1 \text{至} i-1\]
很明显写个高精就好了
\(Code:\)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int SIZE = 100;
struct BIGINT {
int num[SIZE];
int cnt;
BIGINT() { memset(num, 0, sizeof(num)), cnt = 0;}
BIGINT operator * (const BIGINT a) const {
BIGINT temp;
temp.cnt = cnt + a.cnt;
for(int i = 1; i <= cnt; i++)
for(int j = 1; j <= a.cnt; j++)
temp.num[i + j - 1] += num[i] * a.num[j];
for(int i = 1; i <= temp.cnt; i++) {
temp.num[i + 1] += temp.num[i] / 10;
temp.num[i] %= 10;
}
while(!temp.num[temp.cnt]) temp.cnt--;
return temp;
}
bool operator > (const BIGINT a) const {
if(cnt != a.cnt) return cnt > a.cnt;
for(int i = cnt; i; i--)
if(num[i] != a.num[i])
return num[i] > a.num[i];
return false;
}
void output() const {
if(cnt == 0) putchar('0');
for(int i = cnt; i; i--)
putchar(num[i] + '0');
putchar('\n');
}
};
const int N = 45, K = 10;
BIGINT f[N][K];
int a[N];
BIGINT get(int l, int r) {
BIGINT temp;
temp.cnt = r - l + 1;
for(int i = r; i >= l; i--)
temp.num[r - i + 1] = a[i];
return temp;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%1d", a + i);
#define max(a, b) (a > b ? a : b)
for(int i = 1; i <= n; i++) {
f[i][0] = get(1, i);
for(int j = 1; j <= min(i - 1, m); j++)
for(int k = j; k < i; k++)
f[i][j] = max(f[i][j], f[k][j - 1] * get(k + 1, i));
}
f[n][m].output();
return 0;
}\(2019.8.8\)
\(1.\) \(P1027 \ Car\)的旅行路线
\(2.\) \(P1034\)矩形覆盖
\(3.\) \(P3879 [TJOI2010]\)阅读理解
\(4.\) \(P1038\)神经网络
\(2019.8.9\)
\(1.\) \(P1039\) 侦探推理
\(2.\) \(P1066 \ 2^k\)进制数
\(3.\) \(P2312\)解方程
\(2019.8.10\)
\(1.\) \(P1041\)传染病控制
\(2.\) \(P1043\)数字游戏
\(2019.8.11\)
\(1.\) \(P1983\)车站分级
\(2.\) \(P1941\)飞扬的小鸟
\(2019.8.12\)
\(1.\) \(P1053\)篝火晚会
\(2019.8.13\)
\(1.\) \(P1054\)等价表达式
\(2019.8.14\)
\(2019.8.15\)
\(1.\) \(P3960\)列队
\(2.\) \(P3953\)逛公园
\(2019.8.16\)
\(1.\)\(P1061 \ Jam\)的计数法
\(2.\)\(P1065\)作业调度方案
\(3.\)\(P1069\)细胞分裂
\(4.\)\(P1072 \ Hankson\)的趣味题
\(5.\)\(P1076\)寻宝
\(6.\)\(P1083\)借教室
\(7.\)\(P1099\)树网的核
\(8.\)\(P2157[SDOI2009]\)学校食堂
\(2019.8.17\)
\(1.\)\(P2331 [SCOI2005]\)最大子矩阵
\(2.\)\(P2216 [HAOI2007]\)理想的正方形
\(3.\)\(P3084 [USACO13OPEN]\)照片Photo
\(4.\)\(P2467 [SDOI2010]\)地精部落
\(5.\)$P1415 $拆分数列