HDU春季第三场
1003
由于箱子的面积只有9，且物品的数量已经被限制在6种以内，有：
- 最多放入9个 \(1 \cdot 1\) 格子。
- 最多放入4个 \(1 \cdot 2\) 格子。
- 最多放入3个 \(1 \cdot 3\) 格子。
- 最多放入1个 \(2 \cdot 2\) 格子。
- 最多放入1个 \(2 \cdot 3\) 格子。
- 最多放入1个 \(3 \cdot 3\) 格子。
于是将原来 \(10^6\) 的格子数量优化到只有19个(只有可能在这19个里面选)，然后对着这9个格子暴力搜索即可。
int n;
struct node{
int l,r,v;
};
struct shape{
int id,l,r;
};
vector<shape> ls = {
{0,1,1},{1,1,2},{2,1,3},
{1,2,1},{3,2,2},{4,2,3},
{2,3,1},{4,3,2},{5,3,3}
};
int res = 0;
node a[mxn];
vector<int> e[6];
bool vis[4][4];
int usd[6];
int p[6] = {9,4,3,1,1,1};
bool check(int r,int c,int h,int w){
if(r+h>3||c+w>3) return false;
for(int i = 0;i < h; i++){
for(int j = 0;j < w; j++){
if(vis[r+i][c+j]) return false;
}
}
return true;
}
void st(int r,int c,int h,int w,bool val){
for(int i = 0;i < h; i++){
for(int j = 0;j < w; j++){
vis[r+i][c+j] = val;
}
}
}
void dfs(int pos,int cur){
if(pos==9){
res = max(res,cur);
return;
}
int x = pos/3,y = pos%3;
if(vis[x][y]==1){
dfs(pos+1,cur);
return;
}
dfs(pos+1,cur);
for(auto [id,h,w] : ls){
if(usd[id]<p[id]&&usd[id]<e[id].size()){
if(check(x,y,h,w)){
st(x,y,h,w,1);
ll val = e[id][usd[id]];
usd[id]++;
dfs(pos+1,cur+val);
usd[id]--;
st(x,y,h,w,0);
}
}
}
}
void LonelyLunar_solve(){
cin>>n;
for(int i = 0;i <= 5; i++){
e[i].clear();
}
res = 0;
for(int i = 1;i <= n; i++){
cin>>a[i].l>>a[i].r>>a[i].v;
if(a[i].l>a[i].r){
swap(a[i].l,a[i].r);
}
if(a[i].l==1){
if(a[i].r==1) e[0].push_back(a[i].v);
else if(a[i].r==2) e[1].push_back(a[i].v);
else e[2].push_back(a[i].v);
}
else if(a[i].l==2){
if(a[i].r==2) e[3].push_back(a[i].v);
else e[4].push_back(a[i].v);
}
else{
e[5].push_back(a[i].v);
}
}
for(int i = 0;i <= 5; i++){
sort(e[i].begin(),e[i].end(),greater<>());
}
dfs(0,0);
cout<<res<<endl;
}
1005
观察操作，本质是"月球异或"一个数本身或者删除一个数，并不会新增数字，也就是说，我们要在已有数组 \(a\) 的基础上，通过有限次"月球异或"得到目标值 \(s\) 。
手玩一下操作过程，发现"月球异或"的操作过程就是模3意义下的不进位加法，于是套上3进制线性基结束。
ll p3[40];
ll n,q;
ll a[mxn];
ll p[40][40];//储存最高位为i的基向量的第j位
bool vis[40];
void insert(ll x){
int a[40];
for(int i = 0;i <= 39; i++){
a[i] = x%3;
x/=3;
}
for(int i = 39;i >= 0; i--){
if(a[i]==0) continue;
if(vis[i]==0){
vis[i] = 1;
int inv = (a[i]==1)?1:2;
for(int j = 0;j <= i; j++){
p[i][j] = (a[j]*inv)%3;
}
return;
}
int inv = 3-a[i];
for(int j = 0;j <= i; j++){
a[j] = (a[j]+p[i][j]*inv)%3;
}
}
}
bool query(ll x){
int a[40];
for(int i = 0;i <= 39; i++){
a[i] = x%3;
x/=3;
}
for(int i = 39;i >= 0; i--){
if(a[i]==0) continue;
if(vis[i]==0) return false;
int inv = 3-a[i];
for(int j = 0;j <= i; j++){
a[j] = (a[j]+p[i][j]*inv)%3;
}
}
return true;
}
void LonelyLunar_solve(){
for(int i = 0;i <= 39; i++) vis[i] = 0;
cin>>n>>q;
for(int i = 1;i <= n; i++){
cin>>a[i];
insert(a[i]);
}
while(q--){
ll s;
cin>>s;
cout<<((query(s))?"Yes":"No")<<endl;
}
}
CR edu188EProblem - E - Codeforces
AI大人把这道题当路边一条踢死了。
定义 \(D(s)\) 为字符串 \(s\) 所有字符转换成数字的和，且由 \(x_0\) 衍生的序列为 \(x_1, x_2, \dots, x_k\)（其中 \(x_k \le 9\)），则必然满足恒等式： \(D(s) = x_1 + H(x_1)\) ，其中 \(H(x)\) 定义为从 \(x\) 开始不断进行“各位数字求和”直至结果 \(\le 9\) 所产生的所有数字序列的数值之和。据定义有：
- 若 \(x \le 9\)：\(H(x) = x\)
- 若 \(x > 9\)：\(H(x) = \text{sum\_digits}(x) + H(\text{sum\_digits}(x))\)
由于 \(|s| \le 10^5\)，最大可能的数字总和 \(D(s)\) 约为 \(9 \times 10^5\)，在此范围内打表预处理，然后就做完了。
int val[mxn];
int H[mxn];
vector<int> lk[mxn+100];//反向查找表，从总和找可能对应的数
void init(){
for(int i = 1;i < mxn; i++){
val[i] = val[i/10]+i%10;
if(i<=9)H[i] = val[i];
else H[i] = val[i]+H[val[i]];
int tmp = i+H[i];
if(tmp<mxn+100) lk[tmp].push_back(i);
}
}
string s;
void LonelyLunar_solve(){
cin>>s;
if(s.size()==1)
cout<<s<<endl
return;
}
vector<int> cnt(10,0);
for(char c : s) cnt[c-'0']++;
int ss = 0;
for(int i = 1;i <= 9; i++){
ss+=cnt[i]*i;
}
for(int x : lk[ss]){
vector<int> tmpcnt = cnt;
int cur = x;
vector<string> res;
bool p = 1;
while(1){
string curr = to_string(cur);
res.push_back(curr);
for(char c : curr){
tmpcnt[c-'0']--;
if(tmpcnt[c-'0']<0){
p = 0;
}
}
if(p==0) break;
if(cur<=9) break;
cur = val[cur];
}
if(p==0) continue;
int fir = -1;//找第一个非0的数做第一位
for(int i = 1;i <= 9; i++){
if(tmpcnt[i]>0){
fir = i;
tmpcnt[i]--;
break;
}
}
if(fir==-1) continue;
string x0 = to_string(fir);
for(int i = 9;i >= 0; i--){
x0.append(tmpcnt[i],'0'+i);
}
cout<<x0;
for(auto i : res) cout<<i;
cout<<endl;
return;
}
}
CR1076FProblem - F - Codeforces
类似题目P3842 [TJOI2007] 线段 - 洛谷
由题意，有：在横坐标+1之前，当前横坐标的所有点都应该被遍历。又有贪心的想法：在当前横坐标点遍历完毕时，一定处在当前纵坐标的最高点或者最低点(反之则存在"走回头路"的行为，并非最优)，因此我们设计 \(dp_{i,\ 0 / 1}\) 表示遍历完前 \(i\) 列的点之后并停在最低点/最高点所花费的最短时间，有 \(dp\) 转移：
\[dp[i][0] = min(dp[i-1][0] + |Y_{min}^{(i-1)} - Y_{max}^{(i)}| \ ,\ dp[i-1][1] + |Y_{max}^{(i-1)} - Y_{max}^{(i)}|) + (X_i - X_{i-1}) + (Y_{max}^{(i)} - Y_{min}^{(i)})
\]
\[dp[i][1] = min(dp[i-1][0] + |Y_{min}^{(i-1)} - Y_{min}^{(i)}| \ ,\ dp[i-1][1] + |Y_{max}^{(i-1)} - Y_{min}^{(i)}|) + (X_i - X_{i-1}) + (Y_{max}^{(i)} - Y_{min}^{(i)})
\]
维护每个 \(x\) 轴的最大值和最小值，按 \(x\) 坐标排序并分组，然后 \(O(n)\)跑一遍就做完了。
int n,Ax,Ay,Bx,By;
void LonelyLunar_solve(){
cin>>n>>Ax>>Ay>>Bx>>By;
map<ll, pair<ll, ll>> c;
vector<pair<ll, ll>> a(n+1);
for(int i = 1;i <= n; i++){
cin>>a[i].first;
}
for(int i = 1;i <= n; i++){
cin>>a[i].second;
if(c.count(a[i].first)==0){ c[a[i].first] = {a[i].second,a[i].second};
}
else{
c[a[i].first].first = min(c[a[i].first].first,a[i].second);
c[a[i].first].second = max(c[a[i].first].second,a[i].second); }
}
ll prex = Ax;
ll premin = Ay;
ll premax = Ay;
ll dp0 = 0;
ll dp1 = 0;
for (auto const& [curx, y] : c) {
ll curym = y.first;
ll curymx = y.second;
ll dist_x = curx - prex;
ll dist_y = curymx - curym;
ll nxtdp0 = min(dp0 + abs(premin - curymx), dp1 + abs(premax - curymx)) + dist_x + dist_y;
ll nxtdp1 = min(dp0 + abs(premin - curym), dp1 + abs(premax - curym)) + dist_x + dist_y;
dp0 = nxtdp0;
dp1 = nxtdp1;
prex = curx;
premin = curym;
premax = curymx;
}
ll lstdis = Bx - prex;
ll res = min(dp0 + abs(premin - By), dp1 + abs(premax - By)) + lstdis;
cout<<res<<endl;
}