A. Alice the Fan
Solved.
题意：
两个人打网球，要求teamA 的得分与其他队伍拉开尽量大
输出合法的方案
思路：
$dp[i][j][k][l] 表示 A 赢i局，其他队伍赢j局，两个人比分为k : l 的时候的方案$
#include<bits/stdc++.h> using namespace std; int dp[][][][];
vector<pair<int, int> >out[][][][]; void Init()
{
dp[][][][] = ;
for(int sum = ; sum <= ; ++sum)
{
for(int l = ; l <= sum; ++l)
{
for(int i = ; i <= ; ++i)
{
for(int j = ; j <= ; ++j)
{
int r = sum - l;
if(!dp[l][r][i][j]) continue;
if(max(l, r) >= ) continue;
int limit = ;
if(sum == ) limit = ;
for(int tmp = limit; tmp <= ; ++tmp)
{
if(i + tmp <= && j + tmp - <= && !dp[l + ][r][i + tmp][j + tmp - ])
{
dp[l + ][r][i + tmp][j + tmp - ] = ;
out[l + ][r][i + tmp][j + tmp - ] = out[l][r][i][j];
out[l + ][r][i + tmp][j + tmp - ].push_back(make_pair(tmp, tmp - ));
}
if(i + tmp - <= && j + tmp <= && !dp[l][r + ][i + tmp - ][j + tmp])
{
dp[l][r + ][i + tmp - ][j + tmp] = ;
out[l][r + ][i + tmp - ][j + tmp] = out[l][r][i][j];
out[l][r + ][i + tmp - ][j + tmp].push_back(make_pair(tmp - , tmp));
}
} for(int tmp = ; tmp <= limit - ; ++tmp)
{
if(i + limit <= && j + tmp <= && !dp[l + ][r][i + limit][j + tmp])
{
dp[l + ][r][i + limit][j + tmp] = ;
out[l + ][r][i + limit][j + tmp] = out[l][r][i][j];
out[l + ][r][i + limit][j + tmp].push_back(make_pair(limit, tmp));
}
if(i + tmp <= && j + limit <= && !dp[l][r + ][i + tmp][j + limit])
{
dp[l][r + ][i + tmp][j + limit] = ;
out[l][r + ][i + tmp][j + limit] = out[l][r][i][j];
out[l][r + ][i + tmp][j + limit].push_back(make_pair(tmp, limit));
}
}
}
}
}
}
} int a, b; int main()
{
Init();
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &a, &b);
int l = -, r = -;
if(dp[][][a][b])
{
l = ;
r = ;
}
else if(dp[][][a][b])
{
l = ;
r = ;
}
else if(dp[][][a][b])
{
l = ;
r = ;
}
else if(dp[][][a][b])
{
l = ;
r = ;
}
else if(dp[][][a][b])
{
l = ;
r = ;
}
else if(dp[][][a][b])
{
l = ;
r = ;
}
if(l == - && r == -)
{
puts("Impossible");
}
else
{
printf("%d:%d\n", l, r);
int len = out[l][r][a][b].size();
for(int i = ; i < len; ++i) printf("%d:%d%c", out[l][r][a][b][i].first, out[l][r][a][b][i].second, " \n"[i == len - ]);
}
}
return ;
}
B:Bimatching
Unsolved.
题意：
$有n个男生和m个女生，一个男生要找两个女生组成一个三元祖进行跳舞$
$当且仅当那个男生同时喜欢另两个女生的时候，他们可以组成三元祖跳舞$
$求最多的三元祖个数$
C:Cactus Search
Unsolved.
D:Distance Sum
Unsolved.
题意：
给出一张无向图，求$\sum_{1 <= i <= n} \sum_{1 <= j <= i} d(i, j) $
E：Easy Chess
Solved.
题意：
从左下角出发到右上角，每个点只能停留一次，且必须停留n次
给出方案
思路：
暴力构造
最后一轮的时候注意绕一个圈
#include<bits/stdc++.h> using namespace std; int n; int main()
{
while(~scanf("%d", &n))
{
if(n == )
cout << "a1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 g5 g6 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 g5 g6 g7 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g2 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g2 g3 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g2 g3 g4 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g2 g3 g4 g5 g8 h8" << endl;
else if(n == )
cout << "a1 a2 a3 a4 a5 a6 a7 a8 b8 b7 b6 b5 b4 b3 b2 b1 c1 c2 c3 c4 c5 c6 c7 c8 d8 d7 d6 d5 d4 d3 d2 d1 e1 e2 e3 e4 e5 e6 e7 e8 f8 f7 f6 f5 f4 f3 f2 f1 h1 h2 h3 h4 h5 h6 h7 g7 g1 g2 g3 g4 g5 g6 g8 h8" << endl;
}
return ;
}
F. Fractions
Solved.
题意：
$令b_i为n的因数$
$求找到k对 a_i 和 b_i$
使得
$\sum_{i = 1}^{k} \frac {a_i}{b_i} = 1 - \frac{1}{n}$
思路：
显然，我们只需要找到两对
令其为$a_1, b_1, a_2, b_2$
有$\frac{a_1}{b_1} + \frac{a_2}{b_2} = \frac{n - 1}{n}$
有$\frac{a_1 \cdot b_2 + a_2 \cdot b_1} {b_1 \cdot b_2} = \frac{n - 1}{n}$
有 $n = b_1 \cdot b_2$
那么$b_1 = \frac{n}{b_2}$
代入其中 得到
$a_1 \cdot b_2 + \frac{a_2 \cdot n} {b_2} = n - 1$
$固定b_2 枚举a_1 求解 或者 exgcd 也可以$
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n; int main()
{
while(~scanf("%lld", &n))
{
ll tmp = n;
vector<ll>vec;
for(ll i = ; i * i <= tmp; ++i)
{
if(tmp % i == )
{
ll res = ;
while(tmp % i == )
{
tmp /= i;
res *= i;
}
vec.push_back(res);
}
}
if(tmp != ) vec.push_back(tmp);
if(vec.size() <= )
{
puts("NO");
}
else
{
puts("YES\n2");
ll num1 = vec[];
for(ll i = ; ; ++i)
{
ll num2 = n - - n / num1 * i;
if(num2 % num1 == )
{
printf("%lld %lld\n", i, num1);
printf("%lld %lld\n", num2 / num1 , n / num1);
break;
}
}
}
}
return ;
}
G. Guest Student
Water.
#include<bits/stdc++.h> using namespace std; typedef long long ll;
const int INF = 0x3f3f3f3f;
ll n;
int used[]; int main()
{
int t;
scanf("%d", &t);
while(t--)
{
ll tot = ;
scanf("%lld", &n);
for(int i = ; i <= ; ++i)
{
scanf("%d", used + i);
tot += used[i];
used[i + ] = used[i];
}
ll tmp = (n - ) / tot;
ll ans = * tmp;
ll remind = n - tmp * tot;
ll res = INF;
for(int i = ; i <= ; ++i)
{
if(used[i])
{
ll pos = i;
ll tmp = ;
while(tmp < remind) tmp += used[pos++];
res = min(res, pos - i);
}
}
printf("%lld\n", ans + res);
}
return ;
}
#include <bits/stdc++.h>
using namespace std; #define INF 0x3f3f3f3f
int used[], fa[];
int t, n; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
memset(used, , sizeof used);
memset(fa, , sizeof fa);
int tot = ;
int pre = ;
for (int i = ; i <= ; ++i)
{
scanf("%d", used + i);
tot += used[i];
fa[i] = pre;
if (used[i]) pre = i;
}
for (int i = ; i <= ; ++i) used[i] = used[i - ];
int remind = n % tot, need = (remind ? n / tot : n / tot - ) * , res = INF;
if (!remind) remind = tot;
for (int i = ; i <= ; ++i) if (used[i])
{
int cnt = , tmp = ;
for (int j = i; j <= && cnt < remind; ++j)
{
cnt += used[j];
++tmp;
}
if (cnt == remind) res = min(res, need + tmp);
}
printf("%d\n", res);
}
return ;
}
H:Harder Satisfiability
Unsolved.
I. Interval-Free Permutations
Unsolved.
J. JS Minification
Unsolved.
K. King Kog's Reception
Upsoved.
题意：
维护一个队列，骑士在$a_i时刻进入，并且占用b_i的时间， 求从t_i时刻进入需要等待多少时间才能轮到$
思路：
发现$t_i完事的时间为Max_j <= i(a_j + \sum_{j <= k <= i} b_i)$ 然后线段树维护
置于为什么是这样
我们考虑如果我们选取的$a_j 到 a_i 中间有空白时间段的话，那么后移j肯定使得值更优$
$否则有重叠部分的话，不会有问题$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1000010
int q;
int p[N], v[N]; namespace SEG
{
struct node
{
ll sum, Max;
node ()
{
sum = Max = ;
}
node operator + (const node &other) const
{
node res;
res.sum = sum + other.sum;
res.Max = max(other.Max, Max + other.sum);
return res;
}
}a[N << ], res;
void build(int id, int l, int r)
{
a[id] = node();
if (l == r)
{
a[id].sum = ;
a[id].Max = l;
return;
}
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
a[id] = a[id << ] + a[id << | ];
}
void update(int id, int l, int r, int pos, int val)
{
if (l == r)
{
a[id].sum += val;
a[id].Max += val;
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(id << , l, mid, pos, val);
else update(id << | , mid + , r, pos, val);
a[id] = a[id << ] + a[id << | ];
}
void query(int id, int l, int r, int ql, int qr)
{
if (l >= ql && r <= qr)
{
res = res + a[id];
return;
}
int mid = (l + r) >> ;
if (ql <= mid) query(id << , l, mid, ql, qr);
if (qr > mid) query(id << | , mid + , r, ql, qr);
}
} int main()
{
while (scanf("%d", &q) != EOF)
{
SEG::build(, , );
char op; int x, y;
for (int i = ; i <= q; ++i)
{
scanf(" %c%d", &op, p + i);
if (op == '+')
{
scanf("%d", v + i);
SEG::update(, , , p[i], v[i]);
}
else if (op == '-')
SEG::update(, , , p[p[i]], -v[p[i]]);
else
{
SEG::res = SEG::node();
SEG::query(, , , , p[i]);
printf("%lld\n", SEG::res.Max - p[i]);
}
}
}
return ;
}
L. Lazyland
Water.
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + ; int n, k;
ll vis[maxn];
ll arr[maxn], brr[maxn]; int main()
{
while(~scanf("%d %d", &n, &k))
{
for(int i = ; i <= k; ++i) vis[i] = -;
for(int i = ; i <= n; ++i) scanf("%lld", arr + i);
for(int i = ; i <= n; ++i) scanf("%lld", brr + i);
priority_queue<ll, vector<ll>, greater<ll> >q;
int cnt = ;
for(int i = ; i <= n; ++i)
{
if(vis[arr[i]] == -)
{
cnt++;
vis[arr[i]] = i;
}
else
{
ll tmp = brr[vis[arr[i]]];
if(tmp < brr[i])
{
q.push(tmp);
vis[arr[i]] = i;
}
else
{
q.push(brr[i]);
}
}
}
ll ans = ;
for(int i = cnt + ; i <= k; ++i)
{
ans += q.top();q.pop();
}
printf("%lld\n", ans);
}
return ;
}
M:Minegraphed
Upsolved.
题意：
构造一个矩形，使得点的连通性和所给的图一致
思路：
用一个三层的图，一个 $(3 \cdot n - 2) * 3 的截面 第三层用小沟单向连接$
$有多少条边就增加多少小沟，注意用一条横线隔开，前面预留2行为数字$
#include <bits/stdc++.h>
using namespace std; #define N 1010
int n, m, G[][];
char ans[N], tmp[N]; int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int w = * n - , m = ;
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) scanf("%d", G[i] + j), m += G[i][j];
printf("%d %d %d\n", w, (m << ) + , );
for (int i = ; i <= w; ++i) tmp[i] = '#'; tmp[w + ] = ;
puts(tmp + ); puts(tmp + );
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) if (G[i][j])
{
puts(tmp + );
memcpy(ans, tmp, sizeof tmp);
int l = (i - ) * + , r = (j - ) * + ;
if (l > r) swap(l, r);
for (int k = l; k <= r; ++k) ans[k] = '.';
puts(ans + );
}
puts("");
puts(tmp + );
puts(tmp + );
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) if (G[i][j])
{
puts(tmp + );
memcpy(ans, tmp, sizeof tmp);
int l = (i - ) * + , r = (j - ) * + ;
ans[l] = ans[r] = '.';
if (l < r) ans[l + ] = '.';
else ans[l - ] = '.';
puts(ans + );
}
puts("");
memcpy(ans, tmp, sizeof tmp);
for (int i = , j = ; i <= w; i += , ++j) ans[i] = j + '', tmp[i] = '.';
puts(ans + );
puts(tmp + );
for (int i = ; i <= n; ++i) for (int j = ; j <= n; ++j) if (G[i][j])
puts(tmp + ), puts(tmp + );
}
return ;
}