Preface
队友C麻了我直接3h下班雀魂启动，如果时间多点感觉还有AK希望
不过不得不说北美场难度都集中在模拟题上了，一般压轴都是数学或者几何，而这类题目遇到徐神祁神就是洒洒水了
A. All in the Family
出题人真是丧心病狂，不过这题只是看起来恶心实际写起来感觉还好
做法本身由于树的点数很少，找LCA什么的都可以暴力
只不过输出答案的时候要多讨论讨论，按照题目里给出的一个个判断即可
要注意的是在输出cousins关系时不要把输出的两个人搞反了，算是个很隐蔽的坑点
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int nn,mm,idx,fa[N],dep[N]; map <string,int> rst; string name[N]; vector <int> v[N];
inline void DFS(CI now)
{
for (auto to:v[now]) dep[to]=dep[now]+1,DFS(to);
}
inline int getLCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
while (dep[x]>dep[y]) x=fa[x];
if (x==y) return x;
while (x!=y) x=fa[x],y=fa[y];
return x;
}
int main()
{
//freopen("A.out","w",stdout);
ios::sync_with_stdio(false); cin.tie(0);
auto ID=[&](const string& s)
{
if (rst.count(s)) return rst[s];
return rst[s]=++idx;
};
RI i,j; for (cin>>nn>>mm,i=1;i<=nn;++i)
{
string s; cin>>s; int x=ID(s),y;
for (cin>>y,j=1;j<=y;++j)
{
string t; cin>>t; int z=ID(t);
fa[z]=x; v[x].push_back(z);
}
}
int rt; for (i=1;i<=idx;++i) if (!fa[i]) { rt=i; break; }
//for (i=1;i<=idx;++i) for (auto j:v[i]) printf("%d -> %d\n",i,j);
for (DFS(rt),i=1;i<=mm;++i)
{
string s,t; cin>>s>>t; int x=ID(s),y=ID(t);
int z=getLCA(x,y),m=dep[x]-dep[z],n=dep[y]-dep[z];
bool flag=0; if (m>n) swap(m,n),swap(x,y),swap(s,t),flag=1;
auto trs=[&](CI x)
{
string s=to_string(x);
if (x>=11&&x<=13) return s+"th";
if (x%10==1) return s+"st";
if (x%10==2) return s+"nd";
if (x%10==3) return s+"rd";
return s+"th";
};
if (m==0)
{
if (n==1) { cout<<t<<" is the child of "<<s<<endl; continue; }
cout<<t<<" is the "; for (j=1;j<=n-2;++j) cout<<"great ";
cout<<"grandchild of "<<s<<endl; continue;
}
if (m==n)
{
if (n==1) cout<<s<<" and "<<t<<" are siblings"<<endl;
else cout<<s<<" and "<<t<<" are "<<trs(n-1)<<" cousins"<<endl; continue;
}
if (flag) swap(s,t);
if (n-m==1) cout<<s<<" and "<<t<<" are "<< trs(m-1)<<" cousins, 1 time removed"<<endl;
else cout<<s<<" and "<<t<<" are "<<trs(m-1)<<" cousins, "<<n-m<<" times removed"<<endl;
}
return 0;
}
B. Kinky Word Searches
本来想抢这题一血的，可惜没抢到
做法很简单，直接大力DP，\(f_{i,j,x,y,d}\)表示当前匹配了\(s\)的前\(i\)个字符，转向了\(j\)次，在方格中\((x,y)\)位置，面朝的方向为\(d\)的状态是否可达
转移的时候再枚举一个方向即可，注意特判第一步的走法
#include<cstdio>
#include<iostream>
#include<cctype>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=12,dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
int n,m,t,len; char a[N][N],s[105]; bool f[105][105][N][N][8];
int main()
{
RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) for (j=1;j<=m;++j)
{
char ch; while (ch=getchar(),!isalpha(ch)); a[i][j]=ch;
}
scanf("%d%s",&t,s+1); len=strlen(s+1); t=min(len,t);
for (i=1;i<=n;++i) for (j=1;j<=m;++j)
if (a[i][j]==s[1]) for (k=0;k<8;++k) f[1][0][i][j][k]=1;
for (i=1;i<len;++i) for (j=0;j<=min(t,i-1);++j)
for (int x=1;x<=n;++x) for (int y=1;y<=m;++y) for (k=0;k<8;++k)
if (f[i][j][x][y][k])
{
for (int d=0;d<8;++d)
{
int nx=x+dx[d],ny=y+dy[d];
if (nx<1||nx>n||ny<1||ny>m) continue;
if (a[nx][ny]==s[i+1]) f[i+1][j+(i!=1&&k!=d)][nx][ny][d]=1;
}
}
bool flag=0; for (i=1;i<=n;++i) for (j=1;j<=m;++j)
for (k=0;k<8;++k) flag|=f[len][t][i][j][k];
return puts(flag?"YES":"NO"),0;
}
C. Math Trade
祁神开场写的签到
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int n;
vector<int> G[N];
map<string, int> mp; int idx=0;
int ans=0;
bool vis[N];
void dfs(int x, int dep){
vis[x]=true;
for (int v : G[x]){
if (vis[v]) ans = max(ans, dep);
else dfs(v, dep+1);
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=1; i<=n; ++i){
int a, b;
string str;
cin >> str;
cin >> str; if (!mp.count(str)) mp[str] = ++idx; a=mp[str];
cin >> str; if (!mp.count(str)) mp[str] = ++idx; b=mp[str];
G[a].push_back(b);
}
for (int i=1; i<=n; ++i){
if (!vis[i]) dfs(i, 1);
}
if (ans>0) cout << ans << '\n';
else cout << "No trades possible\n";
return 0;
}
D. Oreperations Research
大暴力题，敢写敢过
注意到有效的状态数很少，当前火车的车厢号，A/B开头的位置即可唯一确定一个状态，这样是\(O(nrs)\)的
转移不妨再\(O(rs)\)大力枚举A/B向后转移的状态，剩下的部分就是用若干个A的和以及B的和来凑
直接预处理个完全背包把所有有解的数求出来即可，套个bitset优化硬艹\(2\times 10^6\)也不是不行
#include <bits/stdc++.h>
int r, s, n;
int a[100], b[100], c[100], as, bs;
bool dp[100][50][50];
std::bitset<2000001> hkr;
int main(void) {
std::ios::sync_with_stdio(false);
std::cin >> r >> s >> n;
for(int i = 0; i < r; ++i) std::cin >> a[i], a[i + r] = a[i];
for(int i = 0; i < s; ++i) std::cin >> b[i], b[i + s] = b[i];
for(int i = 0; i < n; ++i) std::cin >> c[i];
for(int i = 1; i < 2 * r; ++i) a[i] += a[i - 1];
for(int i = 1; i < 2 * s; ++i) b[i] += b[i - 1];
as = a[r - 1], bs = b[s - 1];
hkr[0] = true;
for(int i = 1; i <= 2000000; ++i) {
if(i >= as) hkr[i] = hkr[i] || hkr[i - as];
if(i >= bs) hkr[i] = hkr[i] || hkr[i - bs];
}
// std::cerr << "as = " << as << ", bs = " << bs << char(10);
dp[0][0][0] = true;
for(int i = 0; i < n; ++i) for(int j = 0; j < r; ++j) for(int k = 0; k < s; ++k) if(dp[i][j][k]) {
// std::cerr << "dp[" << i << "][" << j << "][" << k << "] == true\n";
for(int l = j; l < j + r; ++l) for(int m = k; m < k + s; ++m) {
int cargo = c[i];
if(l) cargo -= a[l - 1]; if(m) cargo -= b[m - 1];
if(j) cargo += a[j - 1]; if(k) cargo += b[k - 1];
// std::cerr << "cargo[" << l << "][" << m << "] = " << cargo << ", c[" << i << "] = " << c[i] << char(10);
if(cargo < 0 || !hkr[cargo]) continue;
if(i + 1 == n) return std::cout << "yes" << std::endl, 0;
int x = l, y = m;
if(x >= r) x -= r; if(y >= s) y -= s;
dp[i + 1][x][y] = true;
}
}
std::cout << "no" << std::endl;
return 0;
}
E. Over the Hill, Part 1
Easy Version没啥好说的，模拟就完事了
#include <bits/stdc++.h>
constexpr int mod = 37;
struct mat: public std::vector<std::vector<int>> {
mat(size_t n): vector(n, std::vector<int>(n, 0)) {}
mat operator *(const mat &b) const {
const size_t n = this->size();
mat res(n);
for(size_t i = 0; i < n; ++i) {
for(size_t j = 0; j < n; ++j) {
for(size_t k = 0; k < n; ++k)
res[i][j] += (*this)[i][k] * b[k][j];
res[i][j] %= mod;
}
}
return res;
}
};
std::vector<int> decode(const std::string &s, size_t n) {
std::vector<int> res;
res.reserve(s.size());
for(char c: s) {
if(std::isupper(c)) res.push_back(c - 'A'); else
if(std::isdigit(c)) res.push_back(c - '0' + 26); else
res.push_back(36);
}
while(res.size() % n) res.push_back(36);
return res;
}
std::string encode(const std::vector<int> &s, size_t n) {
std::string res;
res.reserve(s.size());
for(int c: s) {
if(c < 26) res.push_back(c + 'A'); else
if(c < 36) res.push_back(c - 26 + '0'); else
res.push_back(' ');
}
while(res.size() && res.back() == ' ') res.pop_back();
return res;
}
int main(void) {
size_t n; std::cin >> n;
mat a(n); for(auto &a: a) for(auto &a: a) std::cin >> a;
std::string s; while(s.size() == 0) std::getline(std::cin, s);
std::vector<int> t = decode(s, n);
std::vector<int> h;
for(size_t i = 0; i < t.size(); i += n) {
h.assign(n, 0);
// for(int j = 0; j < n; ++j) std::cerr << t[i + j] << char(j == n - 1 ? 10 : 32);
for(size_t j = 0; j < n; ++j) {
for(size_t k = 0; k < n; ++k)
h[j] += a[j][k] * t[i + k];
h[j] %= mod;
}
// for(int j = 0; j < n; ++j) std::cerr << h[j] << char(j == n - 1 ? 10 : 32);
for(size_t j = 0; j < n; ++j) t[i + j] = h[j];
}
std::cout << encode(t, n) << std::endl;
return 0;
}
F. Over the Hill, Part 2
手玩下会发现这玩意就等价于一个矩阵求逆，直接上模意义下的高斯消元板子即可
因为上次我写高消被腐乳的前车之鉴，决定以后都把高消扔给徐神来写了（逃
注意这题对输入的转化比较恶心，同时无解和多解的判断也要留心
#include <bits/stdc++.h>
constexpr int mod = 37;
constexpr std::array<int, 37> inv = ([]() {
std::array<int, 37> inv;
inv[0] = 0;
for(int i = 1; i < 37; ++i) {
inv[i] = 1;
for(int j = 1; j <= 35; ++j) inv[i] = inv[i] * i % mod;
}
return inv;
})();
struct vivi: public std::vector<int> {
vivi (size_t s = 0): vector(s, 0) {}
vivi& operator +=(const vivi &b) {
for(size_t i = 0; i < size(); ++i) (*this)[i] = ((*this)[i] + b[i]) % mod;
return *this;
}
vivi& operator -=(const vivi &b) {
for(size_t i = 0; i < size(); ++i) (*this)[i] = ((*this)[i] - b[i] + mod) % mod;
return *this;
}
vivi& operator *=(int p) {
for(size_t i = 0; i < size(); ++i) (*this)[i] = (*this)[i] * p % mod;
return *this;
}
vivi operator *(int p) const {
vivi c(size());
for(size_t i = 0; i < size(); ++i) c[i] = (*this)[i] * p % mod;
return c;
}
};
std::vector<int> decode(const std::string &s, size_t n) {
std::vector<int> res;
res.reserve(s.size());
for(char c: s) {
if(std::isupper(c)) res.push_back(c - 'A'); else
if(std::isdigit(c)) res.push_back(c - '0' + 26); else
res.push_back(36);
}
while(res.size() % n) res.push_back(36);
return res;
}
std::string encode(const std::vector<int> &s, size_t n) {
std::string res;
res.reserve(s.size());
for(int c: s) {
if(c < 26) res.push_back(c + 'A'); else
if(c < 36) res.push_back(c - 26 + '0'); else
res.push_back(' ');
}
while(res.size() && res.back() == ' ') res.pop_back();
return res;
}
void guass(std::vector<vivi> &a) {
const int n = a.size(), m = a.front().size();
int hkr = 0;
for(int i = 0; i < m && hkr < n; ++i) {
int ars = hkr;
while(ars < n && a[ars][i] == 0) ars += 1;
if(ars == n) continue;
if(hkr != ars) std::swap(a[ars], a[hkr]);
a[hkr] *= inv[a[hkr][i]];
for(int j = 0; j < n; ++j) if(j != hkr && a[j][i])
a[j] -= a[hkr] * a[j][i];
hkr += 1;
}
return ;
}
template<typename It>
bool my_any(It begin, It end) {
while(begin != end) {
if(*begin) return true;
begin ++;
}
return false;
}
int main(void) {
size_t n; std::cin >> n;
std::vector<int> a, b; {
std::string as, bs;
while(as.size() == 0) std::getline(std::cin, as);
while(bs.size() == 0) std::getline(std::cin, bs);
a = decode(as, n), b = decode(bs, n);
}
int l = a.size();
std::vector<vivi> mat(l / n);
for(int i = 0; i < l; i += n) {
vivi lv(2 * n);
for(int j = 0; j < n; ++j) lv[j] = a[i + j], lv[n + j] = b[i + j];
mat[i / n] = std::move(lv);
}
// for(int i = 0; i < mat.size(); ++i) for(int j = 0; j < mat[i].size(); ++j)
// std::cerr << mat[i][j] << char(j == mat[i].size() - 1 ? 10 : 32);
guass(mat);
// for(int i = 0; i < mat.size(); ++i) for(int j = 0; j < mat[i].size(); ++j)
// std::cerr << mat[i][j] << char(j == mat[i].size() - 1 ? 10 : 32);
int m = l / n;
for(int i = 0; i < m; ++i) {
bool flag_l = false, flag_r = false;
for(int j = 0; j < n ; ++j) if(mat[i][j]) { flag_l = true; break; }
for(int j = n; j < 2 * n; ++j) if(mat[i][j]) { flag_r = true; break; }
if(!flag_l && flag_r) return std::cout << "No solution\n", 0;
}
if(m < n) return std::cout << "Too many solutions\n", 0;
for(int i = 0; i < n; ++i) if(mat[i][i] != 1)
return std::cout << "Too many solutions\n", 0;
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j)
std::cout << mat[j][i + n] << char(j == n - 1 ? 10 : 32);
return 0;
}
G. A Rank Problem
签到，模拟一下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int n,m,x,y,a[N];
int main()
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) a[i]=i; getchar();
while (m--)
{
scanf("T%d T%d",&x,&y); getchar();
auto find=[&](CI x)
{
for (RI i=1;i<=n;++i) if (a[i]==x) return i;
};
int px=find(x),py=find(y);
if (px>py)
{
for (i=py;i<px;++i) a[i]=a[i+1]; a[px]=y;
}
}
for (i=1;i<=n;++i) printf("T%d ",a[i]);
return 0;
}
H. Restroom Monitor
徐神开场一眼秒的一个贪心，我题目都没看
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
int s, n; std::cin >> s >> n;
std::vector<int> a, b;
for(int i = 1; i <= n; ++i) {
int d; std::string type;
std::cin >> d >> type;
(type[0] == 'y' ? a : b).push_back(d);
}
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set<int> ocy;
int S = (int)2e9;
for(auto i = a.rbegin(); i != a.rend(); ++i) {
if(*i < S) {
ocy.insert(*i);
S = *i - 1;
} else {
ocy.insert(S--);
}
}
if(ocy.size() && *(ocy.begin()) <= 0) return std::cout << "no\n", 0;
// for(auto o: ocy) std::cerr << o << " "; std::cerr << char(10);
int cur = 0, siz = 0;
for(auto d: b) {
while(siz == 0) siz = s - (ocy.find(++cur) != ocy.end());
if(cur > d) return std::cout << "no\n", 0;
siz -= 1;
}
std::cout << "yes\n";
return 0;
}
I. Scholar's Lawn
压轴几何，但是被祁神一眼秒了
大力找出所有实线和虚线的交点，将这些点作为关键点跑最短路即可
最后祁神差一点就在比赛结束前Rush出来了，有点可惜
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define sd second
using LD = long double;
const LD eps = 1e-8;
const LD INF = 1e18;
int sgn(LD x){return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}
struct Pt{
LD x, y;
LD crs(Pt b)const{return x*b.y-y*b.x;}
LD dot(Pt b)const{return x*b.x+y*b.y;}
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
Pt operator+(Pt b)const{return Pt{x+b.x, y+b.y};}
Pt operator*(LD b)const{return Pt{x*b, y*b};}
bool operator<(Pt b)const{return sgn(x-b.x)!=0 ? sgn(x-b.x)<0 : sgn(y-b.y)<0;}
bool operator==(Pt b)const{return sgn(x-b.x)==0 && sgn(y-b.y)==0;}
LD len(){return sqrtl(x*x+y*y);}
};
int tcross(Pt p, Pt a, Pt b){return sgn((a-p).crs(b-p));}
Pt pt_l_l(Pt p1, Pt v1, Pt p2, Pt v2){ return p1 + v1 * (v2.crs(p1-p2)/v1.crs(v2));}
bool segins(Pt a, Pt b, Pt c, Pt d, Pt &res){
int sg1=tcross(a, b, c);
int sg2=tcross(a, b, d);
int sg3=tcross(c, d, a);
int sg4=tcross(c, d, b);
if (0==sg1 && 0==sg2) return false;
if (sg1*sg2<=0 && sg3*sg4<=0){
res = pt_l_l(a, b-a, c, d-c);
return true;
}else return false;
}
const int N = 1e6+5;
int n;
struct Edge{int v; LD w;};
vector<Edge> G[N];
vector<vector<int>> seg;
vector<Pt> vec; int idx=-1;
Pt S; LD vs;
pair<Pt, Pt> F; LD vf;
vector<pair<int, LD>> goal;
struct Node{
int x; LD d;
bool operator<(Node b)const{return sgn(d-b.d)>0;}
};
bool inD[N];
LD dis[N];
void addEdge(int a, int b, LD w){
// printf("addEdge(%lld %lld %Lf)\n", a, b, w);
G[a].push_back(Edge{b, w});
G[b].push_back(Edge{a, w});
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cout << setiosflags(ios::fixed) << setprecision(10);
cin >> n;
for (int i=1; i<=n; ++i){
Pt a, b; cin >> a.x >> a.y >> b.x >> b.y;
int at = ++idx; vec.push_back(a);
int bt = ++idx; vec.push_back(b);
seg.push_back(vector<int>{at, bt});
}
cin >> S.x >> S.y >> vs;
cin >> F.ft.x >> F.ft.y >> F.sd.x >> F.sd.y >> vf;
int St = ++idx; vec.push_back(S);
int sz = seg.size();
for (int i=0; i<sz; ++i){
int a=seg[i][0], b=seg[i][1];
// printf("i=%lld %Lf %Lf %Lf\n", i, (vec[b]-vec[a]).crs(S-vec[a]), (vec[b]-vec[a]).dot(S-vec[a]), (vec[a]-vec[b]).dot(S-vec[b]));
if (tcross(vec[a], vec[b], S)==0 && sgn((vec[b]-vec[a]).dot(S-vec[a]))>=0 && sgn((vec[a]-vec[b]).dot(S-vec[b]))>=0){
seg[i].push_back(St);
// printf("St=%lld on seg %lld\n", St, i);
}
}
for (int i=0; i<sz; ++i){
for (int j=i+1; j<sz; ++j){
int a=seg[i][0], b=seg[i][1];
int c=seg[j][0], d=seg[j][1];
Pt res;
if (segins(vec[a], vec[b], vec[c], vec[d], res)){
// printf("i=%lld j=%lld res(%Lf %Lf)\n", i, j, res.x, res.y);
int rt = ++idx; vec.push_back(res);
seg[i].push_back(rt);
seg[j].push_back(rt);
}
}
}
for (int i=0; i<sz; ++i){
int a=seg[i][0], b=seg[i][1];
Pt res;
if (segins(F.ft, F.sd, vec[a], vec[b], res)){
// printf("i=%lld res(%Lf %Lf)\n", i, res.x, res.y);
int rt = ++idx; vec.push_back(res);
seg[i].push_back(rt);
goal.push_back(make_pair(rt, (res-F.ft).len()/vf));
}
}
// for (int i=0; i<=idx; ++i) printf("%lld : (%Lf %Lf)\n", i, vec[i].x, vec[i].y);
for (auto vp : seg){
sort(vp.begin(), vp.end(), [&](int a, int b){return vec[a]<vec[b];});
int szp = vp.size();
for (int i=1; i<szp; ++i) addEdge(vp[i-1], vp[i], (vec[vp[i-1]]-vec[vp[i]]).len()/vs);
}
for (int i=0; i<=idx; ++i) dis[i]=INF;
priority_queue<Node> Q;
Q.push(Node{St, 0.0L});
dis[St]=0.0L;
while (!Q.empty()){
auto [x, _] = Q.top(); Q.pop();
if (inD[x]) continue; inD[x]=true;
for (auto [v, w] : G[x]){
if (sgn(dis[x]+w - dis[v])<0){
dis[v] = dis[x]+w;
Q.push(Node{v, dis[v]});
}
}
}
// for (int i=0; i<=idx; ++i) printf("dis[%lld]=%Lf\n", i, dis[i]);
LD ans = INF;
for (auto [id, tim] : goal){
if (sgn(tim-dis[id])>=0){
ans = min(ans, tim);
}
}
if (sgn(INF-ans)>0) cout << ans << '\n';
else cout << "-1\n";
return 0;
}
J. Simply Sudoku
没啥好多的，又是大力模拟题，直接把题目中两种操作实现一个个试就完了
#include<bits/stdc++.h>
using namespace std;
int A[9][9];
bool tbl[9][9][9];
void upd(int x, int y, int c){
for (int i=0; i<9; ++i) tbl[i][y][c]=false;
for (int i=0; i<9; ++i) tbl[x][i][c]=false;
for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) tbl[x/3*3+i][y/3*3+j][c]=false;
for (int k=0; k<9; ++k) tbl[x][y][k]=false;
tbl[x][y][c]=true;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
for (int i=0; i<9; ++i) for (int j=0; j<9; ++j) for (int k=0; k<9; ++k) tbl[i][j][k]=true;
for (int i=0; i<9; ++i) for (int j=0; j<9; ++j){
cin >> A[i][j]; --A[i][j];
if (A[i][j]>=0) upd(i, j, A[i][j]);
}
bool ok=true;
while (ok){
ok=false;
for (int i=0; i<9; ++i) for (int j=0; j<9; ++j) if (-1==A[i][j]){
int cnt=0, val=-1;
for (int k=0; k<9; ++k) if (tbl[i][j][k]) ++cnt, val=k;
if (1==cnt){ok=true; upd(i, j, val); A[i][j]=val;}
else{
for (int k=0; k<9; ++k) if (tbl[i][j][k]){
bool flag=true;
for (int p=0; p<9; ++p) if (p!=i && tbl[p][j][k]) flag=false;
if (flag){ok=true; upd(i, j, k); A[i][j]=k;}
flag=true;
for (int p=0; p<9; ++p) if (p!=j && tbl[i][p][k]) flag=false;
if (flag){ok=true; upd(i, j, k); A[i][j]=k;}
flag=true;
for (int p=0; p<3; ++p) for (int q=0; q<3; ++q){
if (!(i/3*3+p==i && j/3*3+q==j) && tbl[i/3*3+p][j/3*3+q][k]) flag=false;
}
if (flag){ok=true; upd(i, j, k); A[i][j]=k;}
}
}
// printf("A[%d][%d]=%d cnt=%d val=%d\n", i, j, A[i][j], cnt, val);
}
}
ok=true;
for (int i=0; i<9; ++i) for (int j=0; j<9; ++j) if (-1==A[i][j]) ok=false;
cout << (ok ? "Easy\n" : "Not easy\n");
for (int i=0; i<9; ++i){
for (int j=0; j<9; ++j){
if (-1==A[i][j]) cout << ". ";
else cout << A[i][j]+1 << ' ';
}cout << '\n';
}
return 0;
}
K. Weighty Tomes
很经典的问题，这个题的一个等价版本就是扔鸡蛋问题，因此做的时候就以这个为参考
不难想到设状态\(f_{i,j}\)表示要在\(i\)层楼中，用\(j\)个鸡蛋确定答案需要的至少步数
转移就是大力枚举当前局面下第一次投鸡蛋的楼层\(k\)，则有
\[f_{i,j}=\min_\limits{1\le k\le i} [\max(f_{k-1,j-1},f_{i-k,j})+1] \]#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,INF=1e9;
int n,m,f[N][25];
inline int DP(CI x,CI y)
{
if (y==0) return x==0?0:INF;
if (y==1) return x; if (x<=1) return x;
if (~f[x][y]) return f[x][y];
int ret=INF; for (RI i=1;i<=x;++i)
ret=min(ret,max(DP(i-1,y-1),DP(x-i,y))+1);
return f[x][y]=ret;
}
int main()
{
scanf("%d%d",&n,&m); memset(f,-1,sizeof(f));
int ans=DP(n,m),l=INF,r=-INF; printf("%d ",ans);
for (RI i=1;i<=n;++i) if (max(DP(i-1,m-1),DP(n-i,m))+1==ans) l=min(l,i),r=max(r,i);
if (l==r) printf("%d ",l); else printf("%d-%d",l,r);
return 0;
}
L. Workers of the World Unite! Just Not Too Close.
怎么和昨天打的北美场一样是个一眼的二分图带权匹配的题啊
不难发现最后使用的门一定是一段前缀用A，然后剩下的一段后缀用B，那么我们可以直接大力枚举分界点
此时问题转化为工人——门，门——工位的多重匹配问题，由于两边都是完全图且不会相互影响，因此可以独立求解
使用KM求解二分图最小完美匹配，总复杂度\(O(n^4)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55,INF=1e9;
int n,d1[N][N][2],d2[N][N][2];
struct KM
{
int w[N][N],kx[N],ky[N],py[N],vy[N],slk[N],pre[N];
inline int solve(CI n)
{
RI i,j,k; for (i=1;i<=n;++i) ky[i]=py[i]=0;
for (i=1;i<=n;++i) for (j=1;j<=n;++j) kx[i]=max(kx[i],w[i][j]);
for (i=1;i<=n;++i)
{
for (j=0;j<=n;++j) vy[j]=pre[j]=0,slk[j]=INF;
int k=0,p=-1; for (py[k=0]=i;py[k];k=p)
{
int d=INF; vy[k]=1; int x=py[k];
for (j=1;j<=n;++j) if (!vy[j])
{
int t=kx[x]+ky[j]-w[x][j];
if (t<slk[j]) slk[j]=t,pre[j]=k;
if (slk[j]<d) d=slk[j],p=j;
}
for (j=0;j<=n;++j)
if (vy[j]) kx[py[j]]-=d,ky[j]+=d; else slk[j]-=d;
}
for (;k;k=pre[k]) py[k]=py[pre[k]];
}
int ret=0; for (i=1;i<=n;++i) ret+=kx[i]+ky[i];
return -ret;
}
}G1,G2;
inline int solve(CI x)
{
RI i,j; for (j=1;j<=n;++j) for (i=1;i<=n;++i) G1.w[j][i]=-d1[i][j][j>x];
for (i=1;i<=n;++i) for (j=1;j<=n;++j) G2.w[i][j]=-d2[i][j][j>x];
return G1.solve(n)+G2.solve(n);
}
int main()
{
RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i)
for (j=1;j<=n;++j) for (k=0;k<2;++k) scanf("%d",&d1[i][j][k]);
for (i=1;i<=n;++i) for (j=1;j<=n;++j) for (k=0;k<2;++k) scanf("%d",&d2[i][j][k]);
int ans=INF,pos; for (i=0;i<=n;++i)
{
int tmp=solve(i); if (tmp<ans) ans=tmp,pos=i;
}
for (printf("%d\n",ans),solve(pos),i=1;i<=n;++i)
printf("%d %d%c %d\n",i,G1.py[i],G1.py[i]<=pos?'A':'B',G2.py[G1.py[i]]);
return 0;
}
Postscript
北美场题又少又简单，每天早早下班真是美滋滋
标签：std,Central,int,res,back,2020,const,America,size From： https://www.cnblogs.com/cjjsb/p/18005120