A. Computer Game
分析：
输出YES当且仅当，每一列都至少存在一个0.
代码：
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int dp[N];
char mp[2][N];
void solve()
{
int n; scanf("%d",&n);
scanf("%s %s",&mp[0][1],&mp[1][1]);
dp[1] = 1;
qf(i, 2, n)
{
if((mp[0][i] == '0' || mp[1][i] == '0') && dp[i-1] == 1) dp[i] = 1;
else dp[i] = 0;
}
if(dp[n]) printf("YES\n");
else printf("NO\n");
}
int main()
{
int T; scanf("%d",&T);
while(T--) solve();
}
B. Groups
分析:
暴力枚举选取的两天, 然后检查是否可行即可.
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int dp[N];
char a[N][6];
void solve()
{
int n; scanf("%d",&n);
qf(i, 1, n) qf(j, 1, 5) sf("%d",&a[i][j]);
bool f = 0;
qf(i, 1, 5)
{
qf(j, i+1, 5)
{
int x, y, z, d; x = y = z = d = 0;
qf(k, 1, n)
{
if(a[k][i] == 1 && a[k][j] == 0) x++;
else if(a[k][i] == 0 && a[k][j] == 1) y++;
else if(a[k][i] == 1 && a[k][j] == 1) z++;
else d++;
}
if(d != 0) continue;
if( x <= n/2 && y <= n/2 ) f = 1;
}
}
if(f) pf("YES\n");
else pf("NO\n");
}
int main()
{
int T; scanf("%d",&T);
while(T--) solve();
}
C. Delete Two Elements
分析:
不妨设数组和为sum.
不难将问题转化为 求数组a中有多少有序对
<
i
,
j
>
<i,j>
<i,j>使得
a
i
+
a
j
=
=
s
u
m
?
2
/
n
a_i+a_j==sum*2/n
ai?+aj?==sum?2/n
上map即可.
代码:
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
map<int, int> mp;
void solve()
{
mp.clear();
int n; scanf("%d",&n);
LL sum = 0;
qf(i, 1, n)
{
int ai;
sf("%d",&ai);
sum += ai;
if(mp.find(ai) == mp.end()) mp[ai] = 1;
else mp[ai]++;
}
int k = sum * 2 / n;
if( sum * 2 % n != 0 ) { pf("0\n"); return; }
LL ans = 0;
for( auto p = mp.begin(); p != mp.end(); p++ )
{
if(mp.find(k-p->first) == mp.end()) continue;
if(k - p->first == p->first)
{
ans += (p->second) * (LL)(p->second - 1);
}
else
{
ans += p->second * (LL)(mp.find(k-p->first)->second);
}
}
pf("%lld\n",ans/2);
}
int main()
{
int T; scanf("%d",&T);
while(T--) solve();
}
D. Training Session
分析:
求至少符合题中所给两条件之一的情况的个数很难.
不妨求都不符合题中所给两条件的情况的个数, 再拿总的个数去减, 即可出答案.
观察
a
a
x
y
b
b
\begin{matrix} a & a & x \\ y & b & b \end{matrix}
ay?ab?xb?
不难发现, 不符合题中所给两条件的情况必为上式所给形式.
map瞎搞一下即可.
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
vector<int> T[N], D[N];
void solve()
{
LL n; sf("%lld",&n);
qf(i, 1, n) { T[i].clear(); D[i].clear(); }
LL sum = n*(n-1)*(n-2)/6;
qf(i, 1, n)
{
int t, d; sf("%d %d",&t,&d);
T[t].push_back(d);
D[d].push_back(t);
}
LL p2 = 0;
qf(i, 1, n)
{
for(int e: T[i])
{
p2 += (LL)(D[e].size() - 1) * (LL)(T[i].size() - 1);
}
}
pf("%lld\n",sum-p2);
}
int main()
{
int T; scanf("%d",&T);
while(T--) solve();
}
E. Staircases
分析:
不难发现每次翻转一个方块, 受影响的方块有
[
1
,
3
n
?
2
]
[1, 3n-2]
[1,3n?2]个.
记
d
p
[
i
]
[
j
]
[
0
]
dp[i][j][0]
dp[i][j][0] 表示以方块ij结尾的1型阶梯的个数,
d
p
[
i
]
[
j
]
[
1
]
dp[i][j][1]
dp[i][j][1] 表示以方块ij结尾的2型阶梯的个数.
先dp一遍, 把所有方块的状态都算出来, 再对于每个询问暴力更新即可.
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define sf scanf
#define pf printf
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 1024;
LL n, m, q;
LL sum = 0;
LL f[N][N][2];
void show()
{
qf(i, 1, n)
{
qf(j, 1, m)
pf("%lld ",f[i][j][0]+f[i][j][1]-1);
pf("\n");
}
}
void solve()
{
int x, y; sf("%d %d",&x,&y);
if(f[x][y][0])
{
LL t = f[x][y][0], s = f[x][y][1];
f[x][y][0] = f[x][y][1] = 0;
sum -= s+t-1;
for(int i = x, j = y+1, k = 1; i <= n && j <= m; k++)
{
if(k&1 && f[i][j][1]) f[i][j][1] -= t;
else if(!(k&1) && f[i][j][0]) f[i][j][0] -= t;
else break;
sum -= t;
if(k&1) i++;
else j++;
}
for(int i = x+1, j = y, k = 1; i <= n && j <= m; k++)
{
if( k&1 && f[i][j][0]) f[i][j][0] -= s;
else if(!(k&1) && f[i][j][1]) f[i][j][1] -= s;
else break;
sum -= s;
if(k&1) j++;
else i++;
}
}
else
{
LL t = f[x-1][y][1] + 1;
LL s = f[x][y-1][0] + 1;
f[x][y][0] = t;
f[x][y][1] = s;
sum += s+t-1;
for(int i = x, j = y+1, k = 1; i <= n && j <= m; k++)
{
if(k&1 && f[i][j][1]) f[i][j][1] += t;
else if(!(k&1) && f[i][j][0]) f[i][j][0] += t;
else break;
sum += t;
if(k&1) i++;
else j++;
}
for(int i = x+1, j = y, k = 1; i <= n && j <= m; k++)
{
if(k&1 && f[i][j][0]) f[i][j][0] += s;
else if(!(k&1) && f[i][j][1]) f[i][j][1] += s;
else break;
sum += s;
if(k & 1) j++;
else i++;
}
}
printf("%lld\n",sum);
}
int main()
{
sf("%lld %lld %lld",&n,&m,&q);
sum = 0;
qf(i, 1, n) qf(j, 1, m)
{
f[i][j][0] = f[i-1][j][1] + 1;
f[i][j][1] = f[i][j-1][0] + 1;
sum += f[i][j][0] + f[i][j][1] - 1;
}
while(q--) solve();
}
F. RBS
分析:
考虑dp.
记
d
p
[
t
]
dp[t]
dp[t]为以t为压缩状态(即, t的第i位是否为1表示第i个字符串有没有被使用), 所有包含在t状态的字符串收尾相连 ,最多的RBS前缀个数.
显然
d
p
[
0
]
=
0
dp[0] = 0
dp[0]=0
记
δ
[
i
]
\delta[i]
δ[i] 为第i个字符串的左括号数减去右括号数.
记
m
i
n
_
δ
[
i
]
min\_\delta[i]
min_δ[i] 为第i个字符串中所有前缀中最小的 左括号数减去右括号数.
记
a
[
i
]
[
j
]
a[i][j]
a[i][j] 为第i个字符串的所有( (左括号数-右括号数) = j ) 的前缀的编号集合.
关于前缀的编号, 不妨以其结束的字符的下标做为其编号.
考虑我们dp到状态
t
t
t时, 记集合
T
T
T表示状态t所使用的字符串,
d
i
f
dif
dif表示集合T所有字符串的左括号数减右括号数的和.
值得注意的是, 我们对dp[t]的定义是, 使用在集合T中所有的字符串按照任意可能的顺序相连, 最多的RBS前缀的个数.
特别的, 我们要使用dp[t]去更新下一个状态, 所以dp[t]所代表的相连字符串应该符合 任意前缀的左括号数减右括号数不小于0.
否则, 无论在状态t所代表的字符串添加任何字符串都无法更新答案.
因此, 我们拿一个不属于集合
T
T
T的字符串
s
i
s_i
si?去尝试更新状态t的后继时, 有两种情况:
- 新构造的相连字符串依然符合 任意前缀的左括号数减右括号数不小于0 的性质, 那么更新状态
d
p
[
t
∣
2
i
]
dp[t|2^i]
dp[t∣2i]
- 新构造的相连字符串不符合上述性质, 那么
d
p
[
t
]
+
s
i
的
贡
献
dp[t]+s_i的贡献
dp[t]+si?的贡献是一种可行答案, 更新答案, 但不更新状态.
也就是说我们从状态
t
=
0
t= 0
t=0开始dp, 最后中途算出的答案和
d
p
[
2
n
?
1
]
dp[2^n-1]
dp[2n?1]中的最大者为最终答案.
用数学归纳法不难证明上述每一步的正确性.
算法复杂度为
O
(
m
+
2
n
n
l
o
g
m
)
O(m+2^nnlogm)
O(m+2nnlogm), 其中
m
=
∑
l
e
n
(
s
i
)
m = \sum len(s_i)
m=∑len(si?)
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <assert.h>
using namespace std;
#define close(); ios::sync_with_stdio(false);
#define endl "\n"
#define qf(i, l, r) for(int i = l; i <= r; i++)
#define qdf(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int main()
{
int n; cin >> n;
vector<string> s(n);
vector<vector<vector<int>>> a(n);
vector<int> del(n);
vector<int> min_del(n);
qf(i, 0, n-1)
{
cin >> s[i];
int len = s[i].size();
int x = len;
a[i].resize(len*2+1);
qf(j, 0, len-1)
{
x += (s[i][j]=='('?1:-1);
a[i][x].push_back(j+1);
min_del[i] = min(min_del[i], x-len);
}
del[i] = x-len;
}
vector<int> dp(1<<n, -1);
dp[0] = 0;
int ans = 0;
qf(t, 0, (1<<n)-1)
{
if(dp[t] == -1) continue;
int dif = 0;
qf(i, 0, n-1) if(t & (1<<i)) dif += del[i];
qf(i, 0, n-1)
{
if(t & (1<<i)) continue;
int x = s[i].size() - dif;
int now = dp[t];
if(dif + min_del[i] < 0)
{
int val = a[i][x-1][0];
now += (int)(lower_bound(a[i][x].begin(), a[i][x].end(), val) - a[i][x].begin());
ans = max(ans, now);
continue;
}
if(x >= 0 && x <= 2* s[i].size())
now += a[i][x].size();
dp[t | (1<<i)] = max(dp[t | (1<<i)], now);
ans = max(ans, dp[t | (1<<i)]);
}
}
cout << ans << endl;
}
|