第一场
https://ac.nowcoder.com/acm/contest/46800#question
A:
题目:
按照 ABABABABAB, 来点球,问你在第几球结束比赛,或者没有分出胜负。
思路:
如果胜场少的一方后面都赢了,还是无法胜场大于另一方,那么已经结束比赛。
否则到最后都没分出胜负
代码
void solved()
{
cin >> s + 1;
int A, B;
A = B = 0;
bool flag = false;
for(int i = 1; i <= 10; i++)
{
if(i % 2 != 0 && s[i] == '1')
A++;
if(i % 2 == 0 && s[i] == '1')
B++;
if(A > B)
{
if(A > B + (10 - i) / 2 + (i % 2))
{
flag = true;
cout << i << endl;
return;
}
}
if(B > A)
{
if(B > A + (10 - i) / 2)
{
flag = true;
cout << i << endl;
return;
}
}
}
if(!flag)
{
cout << -1 <<endl;
}
}
C:
题目:
略
思路:
不难发现,对于所有引用量 > 0, 的文章,都各自找一人发表,这样是最多的情况。
代码
void solved()
{
int n;
cin >> n;
int ans = 0;
for(int i = 0; i < n; i++)
{
cin >> a[i];
if(a[i]) ans++;
}
cout <<ans << endl;
}
F:
题目:
现在存在一些树,存在一些点上有炸弹,我们找到一组方案 S T, S 为终点 T 为七点,使得我们必须经过有炸弹的点。
思路:
题目只要求方案数,所以只需要判断是否炸弹都在一个连通块内,或者不存在炸弹。
因为炸弹可以随便放,所以个数不影响答案。
对于炸弹所在连通块的数量 > 1, 那么无论如何也不能找到一个路径使得都经过。
如果数量 == 1, 那么连通块内任意两个点都可以,为连通块内点的数量 ^ 2
如果数量 == 0, 那么任意连通块都可,任意连通块参考上面
代码
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if(pa != pb)
{
p[pa] = pb;
cnt[pb] += cnt[pa];
}
}
int p = 0;
int ans = 0;
int ans2 = 0;
for(int i = 1; i <= n; i++)
{
int x, px;
cin >> x;
if(x)
{
px = find(i);
if(!bom[px])
{
p++;
ans += cnt[px] * cnt[px];
bom[px] = true;
}
}
if(i == find(i)) ans2 += cnt[i] * cnt[i];
}
if(!p)
{
cout << ans2 << endl;
}else if(p == 1) cout << ans <<endl;
else cout << 0 << endl;
}
G:
题目:
略
思路:
不难发现是区间操作,由此想到线段树,但是因为根号操作不满足线段树内合并,所以只能单点操作。
但是单点操作时间复杂度是不够的。
对于根号操作,我们打表发现,所有的数字都会归于一个数字,所以有很多操作是多余的,如果说当前操作的
数字已经归于终点,那么没必要操作了。
代码
int f(int x)
{
return round(10 * sqrt(x));
}
void push_up(int u)
{
tr[u].sum = tr[u << 1]. sum + tr[u << 1 | 1].sum;
tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
}
void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, a[l], 0, 0};
return;
}
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void modify(int u, int l, int r, int k)
{
int lr = (tr[u].r - tr[u].l + 1);
if(tr[u].flag) return;
if(tr[u].l == tr[u].r)
{
for(int i = 0; i < k; i++)
{
int last = tr[u].sum;
tr[u].sum = f(tr[u].sum);
if(last == tr[u].sum)
{
tr[u].flag = true;
break;
}
}
}else
{
int mid = tr[u].r + tr[u].l >> 1;
if(mid >= l) modify(u << 1, l, r, k);
if(r > mid) modify(u << 1 | 1, l, r, k);
push_up(u);
}
}
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int i = 0; i < m; i++)
{
int op, l, r, k;
cin >> op;
if(op == 1)
{
cin >> l >> r >> k;
modify(1, l, r, k);
}else
{
cout << tr[1].sum << endl;
}
}
}
H:
题目:
略
思路:
因为题目保证了拼图是完好的,所以最终都会一个凸出对于一个凹下去。
所以我们统计目前给出的拼图的 凸凹个数,然后差来找到对应成本
代码
void solved()
{
cin >> n;
int p1 = 0, p2 = 0;
for(int i = 0; i < n * n - 1; i++)
{
cin >> ss[i];
int np1 = 0, np2 = 0;
for(int j = 0; j < 4; j++)
{
if(ss[i][j] == '1') p1++;
else if(ss[i][j] == '2')p2++;
}
}
cout << p1 - p2 + 10<< endl;
}
K:
题目:
略
思路:
首先我们优先考虑最多放置1的,满足 0 个坏区间。
发现 1 0 0 1 0 0 1,这样放置是边界 0 个坏区间,然后接下来放一定会出现坏区间。
那么我们贪心的来说接下来肯定是连续放置1,尽可能在一个区间内。
因为后面可能出现 1 00 1 0,而前面的 1 0 0,已经固定,所以我们从后面开始放。
然后统计坏区间即可
代码
void solved()
{
int n, m;
cin >> n >> m;
string s = "";
if((n - 1) / 3 + 1 >= m)
{
cout << 0 << endl;
return;
}
for(int i = 0; i < n; i++)
s += '0';
int sum = 2;
int pos = 0 ;
for(int i = 0; i < n; i++)
{
sum++;
if(sum == 3) s[i] = '1', sum = 0, pos++;
if(pos == m)
break;
}
sum = 0;
for(int i = n - 1; i >= 0; i--)
{
if(sum + pos == m) break;
if(s[i] == '0')
{
s[i] = '1';
sum++;
}
}
int ans = 0;
for(int i = 0; i < n; i++)
{
if(i + 2 == n) break;
int sum = 0;
for(int j = i; j < i + 3; j++)
{
if(s[j] == '1') sum++;
}
if(sum >= 2)
{
ans++;
}
}
cout << ans << endl;
}
代码
void solved()
{
int n, m;
cin >> n >> m;
string s = "";
for(int i = 0; i < n; i++)
s += '0';
int sum = 2;
int pos = 0 ;
for(int i = 0; i < n; i++)
{
sum++;
if(sum == 3) s[i] = '1', sum = 0, pos++;
if(pos == m)
break;
}
sum = 0;
for(int i = n - 1; i >= 0; i--)
{
if(sum + pos == m) break;
if(s[i] == '0')
{
s[i] = '1';
sum++;
}
}
int ans = 0;
for(int i = 0; i < n; i++)
{
if(i + 2 == n) break;
int sum = 0;
for(int j = i; j < i + 3; j++)
{
if(s[j] == '1') sum++;
}
if(sum >= 2)
{
ans++;
}
}
cout << ans << endl;
}
M:
题目:
略
思路:
不难发现,每一个前面的送出多少仙贝都影响后面,所以思考 dp。
状态表示:f[i][j]
表示已经给了 i个人,还剩下 j 个仙贝。
状态转移
首先枚举 i j,其次要枚举当前第 i 个人要给多少仙贝。
所以 f[i][j] = max(f[i][j], f[i - 1][j + k] + (k) / (j + k))
;
最后统计答案,看看给了 n 个人,剩下多少个仙贝的好感度最多。。
代码
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = m; j >= 0; j--)
{
for(int k = 0; k <= m; k++)
{
if(j + k <= m)
f[i][j] = max(f[i][j], f[i - 1][j + k] + (k * 1.0 /(j + k)));
}
}
}
long double ans = 0;
for(int i = 0; i <= m; i++) ans = max(ans, f[n][i]);
printf("%.8llf",ans);
}