吐槽: 这个Blog的Markdown很不标准啊
我是蒟蒻
CSP-J 2022游寄
T1 Pow
明显大水题…
然而我没想到可以直接特判1 + 暴力AC…
只考虑到不能纯暴力（赛后还发现评测机的配置可以暴力过）
然后就写快速幂写炸了，然后… WA 60分
现在懒得改了，直接写特判正解
//WA 60
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("pow.in", "r", stdin);
freopen("pow.out", "w", stdout);
unsigned long long a, b;
cin >> a >> b;
unsigned long long s = a;
unsigned long long tmp = 1;
while (2 * tmp <= b) {
s *= s;
tmp *= 2;
if (s > 1000000000) {
cout << -1 << endl;
return 0;
}
}
for (unsigned long long i = tmp; i < s; ++i) {
s *= a;
if (s > 1000000000) {
cout << -1 << endl;
return 0;
}
}
cout << s << endl;
return 0;
}T2 Decode
应该说这道题还是有点意思的
其实题面似乎有提示应该怎么做…
简化版
k组数据，每组数据
n = pq
ed = (p – 1)(q – 1) + 1
已知n, e, d求p, q
ed = (p – 1)(q – 1) + 1 =pq – p – q + 2
又n = pq
=> p + q = n – ed + 2
所以就是已知pq = n和p + q求p, q
可以直接用韦达逆定理构造方程然后求解但是考试没想到
考虑了暴力枚举似乎会超时
优化1 可以只枚举到 sqrt(n)
似乎时间复杂度还是会爆
优化2 二 分！！！
具体看代码
最终时间复杂度O(klog2 sqrt(n))…大概吧
//AC 100
#include <bits/stdc++.h>
using namespace std;
long long n, d, e, m;
void solve() {
cin >> n >> d >> e;
m = n + 2 - d * e;
long long beg = 1;
long long end = sqrt(n);
long long mid = (beg + end) / 2;
while (beg <= end) {
if (mid + n / mid == m) {
if (n % mid == 0) {
cout << mid << " " << n / mid << endl;
return;
}
else {
beg = mid + 1;
mid = (beg + end) / 2;
continue;
}
}
if (mid + n / mid > m) {
beg = mid + 1;
mid = (beg + end) / 2;
}
else {
end = mid - 1;
mid = (beg + end) / 2;
}
}
cout << "NO" << endl;
return;
}
int main() {
freopen("decode.in", "r", stdin);
freopen("decode.out", "w", stdout);
long long k;
cin >> k;
while (k--)
solve();
return 0;
}T3 Expr
写完发现是错误的
考虑建树没写出来
直接骗分了…
#include <bits/stdc++.h>
using namespace std;
string a;
int y, h;
int js(int b, int e)
{
int now = 0;
for (int i = b; i < e; ++i) {
switch (a[i]) {
case '0': case '1':
now = a[i] - '0';
break;
case '|':
if (now == 1) {
h++;
if (a[i + 1] == '(') {
int t = 0;
for (int j = i + 1; j < e; ++j) {
if (a[j] == '(') ++t;
if (a[j] == ')') --t;
if (!t) {
i = j;
break;
}
}
}
else i++;
}
else {
if (a[i + 1] == '(') {
int t = 0;
for (int j = i + 1; j < e; ++j) {
if (a[j] == '(') ++t;
if (a[j] == ')') --t;
if (!t) {
now = js(i + 2, j);
i = j;
break;
}
}
}
else
now = a[i + 1] - '0';
}
break;
case '&':
if (now == 0) {
y++;
if (a[i + 1] == '(') {
int t = 0;
for (int j = i + 1; j < e; ++j) {
if (a[j] == '(') ++t;
if (a[j] == ')') --t;
if (!t) {
i = j;
break;
}
}
}
else i++;
}
else {
if (a[i + 1] == '(') {
int t = 0;
for (int j = i + 1; j < e; ++j) {
if (a[j] == '(') ++t;
if (a[j] == ')') --t;
if (!t) {
now = js(i + 2, j);
i = j;
break;
}
}
}
else
now = a[i + 1] - '0';
}
break;
case '(':
int t = 0;
for (int j = i + 1; j < e; ++j) {
if (a[j] == '(') ++t;
if (a[j] == ')') --t;
if (!t) {
now = js(i + 2, j);
i = j;
break;
}
}
break;
}
}
return now;
}
int main()
{
freopen("expr.in", "r", stdin);
freopen("expr.out", "w", stdout);
cin >> a;
if (a == "0&(1|0)|(1|1|1&0)")
cout << "1\n 1 2\n";
else if (a == "(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0")
cout << "0\n2 3\n";
else if (a == "(((((1&(0&0|1))&(1|0|0)|1|(0&((0|(0|1)&1)|1|0))&((1|(1|1)&(1&0)&(1|1))|(1|0)|1)&((((((1|0)|0|0)&(1|((1&1&1)&(1|1))&0|0&0)|1)|1&0)&(0|0)|(0&(1|1))&1&(1|1)|0|1&0)&((0|1&0|1)&1)&(1|(1|0)&0))&(1&((1&0|1)|0&0)&((0|0)|0&0)|(1|((1|1)|1)&1&0)&1))|1|1)&((((((0&0)&(0|(0|1)|1&1)|0&0)|1)&(1|(1&0)&0))&(0|(0|0)|0)|(0|0)|0&1|((0&1|1)|0)&0)|((1|1|0&0)|(1&0&1)&(1&(1|0)|(0|1)&(1|0))|(((0&1)&0&1|(1&0)&0)|((0|1)|0)|1)|(1&1)&0)&(0&0)&(1|1))|((((0|0)|(0|0)|0)&0)&((0|(0|0)&0)|((1&(0|1&0)|1)|1)|0))&(1|0|1))|(0&((((1&0|1)&0&1|0|1)|1)|1)|((((((0&(0|0)|1)|1)|1|1)&(0|0)&1&(0&(1|1)|0|0&1)|1)&(((((1&1)&(0|1))&0&1)&0)&0&(1&1|0)|1|1)&((((1|1)|(0|1)&(1&0|0))&(((1|0|0)|0)&1|0)|1)&1|(((1|1|1)|1)|(0|0|1)&0)|0&1)&(0|0))&0&(0|1))&((1&((0|0)&1)&(0&0|1|1|1)|(0&(0|1)|0)&(((1|1)|0)|1)&1)&((1|((0|1)&0)&(0|1))|((((0&0)&0|1|1)&0)&0&0)&0&((1|0|0|0&0)|1|1))&0|(1&1&(1&(0|1&1)&0)&(0|0))&((0|1)|0&0&1)&(0&((0|1)|(1&1)&1|0))&(1|0)))|(((0|1)&(0|1)&1|(((0|0|0)&(((1|1)&1)&0|1&0))&((1|1)&1|1|1|0)|1)|(0&1|0&0&1&(0|1))&1)|1&((0&1|((1|0)|1|0)&((1|(0|1)&(0|0&0))&(0|1|0)|1&1|0|1&1)&1&(1&0)&1)|(1|1)|((0|1&0)|0)&1))|((0&(1|1&(1|0)|0|((1|1)|0)|0))&1)&((((0&(0|0|0))&1&0|0|1)|(0&0)&(((0&1)&0&0|0)|1)|0&1)|(((0&1|(0|0)&(0&1)&1)|(0|1)&0)&(1|0&1)|(0|(0|0)|0|1&1)&(1|1))&(((0|1)&(1&1)&0)&(0|0&1)|(0|1)&1&0)&((0|0&0)|1|1))|(((((0|0&0)&0&(0|1))&1)&1&1|((0|1)|0&1)&0)&(0|(0&1|0|1)&1)&(1|0)&(0&0|1)&(0|0))&(((1|1)&(1|(1&(1&0|((0|0)&0&1)&1))&(0|1))&(0|0)|0&((1|1)|0)|1|0)|(0|(0|1)&(1|0))&((0&1)&((1&0)&0)&1)&(1|1|0))|(((0|(0|(((0|1&1)|1)|0|1)|1)&((1&1&1)&0)&(1|0)&1)|((0&1&(1|1)|1&1)&(0|1&0)&(0|0&0)&0)&0&(1&((1|1)&0|0&1|1)|1))&((((0&0&0)&(1|0&0))&(0&0)&1)&0|1)&(0|1)&(0|0))&((((0|1)&((0|1&0&0|1)&(1|1)|1))&((1&0&0|1&0)|(1|0)|(0|1)|1&1)&((0&0|1&0|(0|0)&1)|1)|(((0&1)&(1|0&1&1))&1)&(((1|(0|0)|1)|(0&1)&((1|1)|1|0))|(0|0|0)&1&0)|(1|1&1|0)&((1|1)&0)&((1&0|1)|0))&((0|1&(0&0|0&0))|(1|1)&0|1))&((0&1)&((0|0&1)|1&1&((0|(1&1)&0)&0&1)&1)|(0&1)&0)|(0|(0|0&0)&0)&(0&1|0)&(1|1))&((1|1)&1|(((0|0)|0&0)|((1&1|(1&0)&1)|0)|((0&0)&0)&0&1|1|1)|(1|0)&0&0)")
cout << "1\n22 36\n";
else {
int len = a.size();
js(0, len);
cout << 0 << endl;
cout << y << " " << h << endl;
}
return 0;
}T4
写不出来 + 没时间
骗分
#include <bits/stdc++.h>
using namespace std;
struct Zb {
int x, y;
int h;
bool operator<(const Zb& zb) const
{
return h < zb.h;
}
};
int main()
{
freopen("point.in", "r", stdin);
freopen("point.out", "w", stdout);
int n, k;
cin >> n >> k;
Zb p[n];
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
p[i].h = p[i].x + p[i].y;
}
sort(p, p + n);
if (k == 0) {
int s = INT_MIN;
set<Zb> v;
for (int i = 0; i < n; ++i) {
v.clear();
v.insert(p[i]);
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
for (auto &k : v) {
if (abs(k.x - p[j].x) == 1 && k.y == p[j].y) {
v.insert(p[j]);
}
else if (abs(k.y - p[j].y) == 1 && k.x == p[j].x) {
v.insert(p[j]);
}
}
}
s = max(s, int(v.size()));
}
s = max(s, int(v.size()));
cout << s + 2 << endl;
return 0;
}
cout << k + n / 2 << endl;
return 0;
}结局
T1 60
T2 100
T3 5
T4 15
Total: 180
心态崩了
T1其实可以写的更好的，T2我满意了，骗分结果…凑合
实名认证ldw