Character Encoding：
https://www.cnblogs.com/zwjzwj/p/14810147.html
Parentheses Matrix：
2和4的时候推出来了，没想到还有>6的情况。。
首先，如果行和列都是奇数，那么不管怎么样都构造不出任何一列和一行满足。
如果行和列只有一个是奇数，那么就去满足偶数的即可。
如果两者都是偶数：
这里使h <= w。
对h分类，h = 2,h = 4和h > 6时分别有不同的最优构造方案。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
inline LL read(){
LL x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
return x*f;
}
}
using namespace FASTIO;
char a[205][205];
int main() {
int ca;ca = read();
while(ca--) {
int h,w;h = read(),w = read();
if(w % 2 != 0 && h % 2 != 0) {
for(int i = 1;i <= h;++i) {
for(int j = 1;j <= w;++j) printf("(");
printf("\n");
}
}
else if(w % 2 != 0 && h % 2 == 0) {
for(int i = 1;i <= h;++i) {
for(int j = 1;j <= w;++j) {
if(i <= h / 2) printf("(");
else printf(")");
}
printf("\n");
}
}
else if(w % 2 == 0 && h % 2 != 0){
for(int i = 1;i <= h;++i) {
for(int j = 1;j <= w;++j) {
if(j <= w / 2) printf("(");
else printf(")");
}
printf("\n");
}
}
else {
int f = 0,ta = 0;
if(h > w) {
swap(h,w);
f = 1;
}
if(h == 2)
for(int i = 0;i < w;i++)
{
a[1][i + 1] = '(';
a[2][i + 1] = ')';
}
else if(h == 4) {
for(int i = 0;i < w;i++)
{
a[1][i + 1] = '(';
a[2][i + 1] = (i < w / 2 ? ')' : '(');
a[3][i + 1] = (i < w / 2 ? '(' : ')');
a[4][i + 1] = ')';
}
}
else
{
for(int i = 0;i < h;i++)
for(int j = 0;j < w;j++)
{
if (i == 0 || j == 0) a[i + 1][j + 1] = '(';
else if (i == h - 1 || j == w - 1) a[i + 1][j + 1] = ')';
else if ((i^j)&1) a[i + 1][j + 1] = ')';
else a[i + 1][j + 1] = '(';
}
}
if(f) {
for(int j = 1;j <= w;++j) {
for(int i = 1;i <= h;++i) printf("%c",a[i][j]);
printf("\n");
}
}
else {
for(int i = 1;i <= h;++i) {
for(int j = 1;j <= w;++j) printf("%c",a[i][j]);
printf("\n");
}
}
}
}
//system("pause");
return 0;
}
View Code
Magic Square：
模拟就行了，一开始被图吓到了。。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 2e5 + 5;
const int M = 1e5 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
inline LL read(){
LL x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
return x*f;
}
}
using namespace FASTIO;
int a[5][5];
void solve(int id,int x) {
if(id == 1) {
int pre = a[1][1];
if(x == 0) {
a[1][1] = a[2][1],a[2][1] = a[2][2],a[2][2] = a[1][2],a[1][2] = pre;
}
else {
a[1][1] = a[1][2],a[1][2] = a[2][2],a[2][2] = a[2][1],a[2][1] = pre;
}
}
else if(id == 2) {
int pre = a[1][2];
if(x == 0) {
a[1][2] = a[2][2],a[2][2] = a[2][3],a[2][3] = a[1][3],a[1][3] = pre;
}
else {
a[1][2] = a[1][3],a[1][3] = a[2][3],a[2][3] = a[2][2],a[2][2] = pre;
}
}
else if(id == 3) {
int pre = a[2][1];
if(x == 0) {
a[2][1] = a[3][1],a[3][1] = a[3][2],a[3][2] = a[2][2],a[2][2] = pre;
}
else {
a[2][1] = a[2][2],a[2][2] = a[3][2],a[3][2] = a[3][1],a[3][1] = pre;
}
}
else {
int pre = a[2][2];
if(x == 0) {
a[2][2] = a[3][2],a[3][2] = a[3][3],a[3][3] = a[2][3],a[2][3] = pre;
}
else {
a[2][2] = a[2][3],a[2][3] = a[3][3],a[3][3] = a[3][2],a[3][2] = pre;
}
}
}
int main() {
int ca;ca = read();
while(ca--) {
int n;n = read();
for(int i = 1;i <= 3;++i) {
string s;cin >> s;
for(int j = 1;j <= 3;++j) a[i][j] = s[j - 1] - '0';
}
while(n--) {
string s;cin >> s;
int id = s[0] - '0';
int ma = (s[1] == 'R');
solve(id,ma);
}
for(int i = 1;i <= 3;++i) {
for(int j = 1;j <= 3;++j) {
printf("%d",a[i][j]);
}
printf("\n");
}
}
//system("pause");
return 0;
}
View Code
Taotao Picks Apples：
一开始觉得想得复杂了，于是一直找简单的方法。结果就是这么复杂。。
首先注意的是，它一定从前往后拿，所以我们可以先找出原始的最优解序列，并打上标记。
首先我们维护出mx[i] - 表示1 ~ i的在最优解里的数的最大下标。
这样当我们更新一个位置时：
如果它不在原始的序列中：
变小了，那么没影响。
变大了，那么去看前面的mx的位置是否还大于它，如果<它了，那么它就插入了这个序列，然后我们去找到后面的在原始序列中的左边的大于它的位置。
如果它在原始的序列中：
变小了，同理看前面再看后面。
变大了，之间看后面。
对于这个后面的位置，我们可以用线段树维护出区间的最大值。然后注意先查左区间，判断无解后再查后区间，这样减枝后复杂度约nlogn。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
inline LL read(){
LL x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
return x*f;
}
}
using namespace FASTIO;
int h[N],dp[N],dp2[N],mx[N];
struct Node{int L,r,mx;}node[N << 2];
void Pushup(int idx) {
node[idx].mx = max(node[idx << 1].mx,node[idx << 1 | 1].mx);
}
void build(int L,int r,int idx) {
node[idx].L = L,node[idx].r = r;
if(L == r) {
node[idx].mx = h[L];
return ;
}
int mid = (L + r) >> 1;
build(L,mid,idx << 1);
build(mid + 1,r,idx << 1 | 1);
Pushup(idx);
}
int query(int L,int r,int k,int idx) {//L ~ r 大于k的最左端的元素
if(node[idx].L == node[idx].r) return node[idx].L;
int mid = (node[idx].L + node[idx].r) >> 1;
int ans = INF;
if(mid >= L && node[idx << 1].mx > k) {
ans = query(L,r,k,idx << 1);
}
if(ans != INF) return ans;
else if(node[idx << 1 | 1].mx > k) ans = query(L,r,k,idx << 1 | 1);
return ans;
}
int main() {
int ca;ca = read();
while(ca--) {
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
memset(mx,0,sizeof(mx));
int n,m;n = read(),m = read();
for(int i = 1;i <= n;++i) h[i] = read();
build(1,n,1);
int pre = h[1],mxpos = 1,tot = 1;
dp2[1] = 1;
for(int i = 2;i <= n;++i) {
mx[i] = mxpos;
if(h[i] > pre) {
dp2[i] = dp2[mxpos] + 1;
pre = h[i];
mxpos = i;
tot++;
}
}
dp[n] = 1;
for(int i = n - 1;i >= 1;--i) {
int ma = query(i + 1,n,h[i],1);
if(ma == INF) dp[i] = 1;
else dp[i] = 1 + dp[ma];
}
while(m--) {
int p,q;p = read(),q = read();
if(h[p] == q) printf("%d\n",tot);
else {
int ans = 0;
if(mx[p] == 0) {
ans++;
int nxt = query(p + 1,n,q,1);
if(nxt != INF) ans += dp[nxt];
}
else {
int ma = h[mx[p]];
if(ma >= q) {
ans += dp2[mx[p]];
int nxt = query(p + 1,n,ma,1);
if(nxt != INF) ans += dp[nxt];
}
else {
ans += dp2[mx[p]] + 1;
int nxt = query(p + 1,n,q,1);
if(nxt != INF) ans += dp[nxt];
}
}
printf("%d\n",ans);
}
}
}
// system("pause");
return 0;
}
/*
2
6 10
2 3 2 4 5 6
1 5
1 3
*/
View Code
From ICPC to ACM：
因为原材料可以无限存，那么对于第i个月的原材料，就可以看成1 ~ i个月里最便宜的原材料。
此时我们还需要考虑的是计算机的存储问题，我们每次都先把这个月能制作的也装入仓库，然后从当前仓库价值小的开始删去。
然后如果超过库存了，我们就从大的位置开始删去即可。
这里因为可能两个位置的值有相同，所以用multiset。但是multiset不支持直接修改，所以我们这里修改需要删掉再插入一个更新的值。
还有就是它删去后的位置是前一个。所以我们要--it，去走到下一个位置。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const int N = 5e4 + 5;
const int M = 1e5 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
inline LL read(){
LL x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
return x*f;
}
}
using namespace FASTIO;
LL c[N],d[N],m[N],p[N],mx[N],rr[N],ee[N];
multiset<pii> s;//val - num
int main() {
int ca;ca = read();
while(ca--) {
int n;n = read();
s.clear();
for(int i = 1;i <= n;++i) c[i] = read(),d[i] = read(),m[i] = read(),p[i] = read();
for(int i = 1;i < n;++i) mx[i] = read(),rr[i] = read(),ee[i] = read();
for(int i = 2;i <= n;++i) c[i] = min(c[i - 1] + rr[i - 1],c[i]);
LL ans = 0,add = 0,tot = 0;//tot - allnum
for(int i = 1;i <= n;++i) {
add += ee[i - 1];
s.insert(pii{c[i] + m[i] - add,p[i]});
tot += p[i];
if(tot < d[i]) {
ans = -1;
break;
}
auto it = s.begin();
while(it != s.end()) {
if(it->second >= d[i]) {
LL val = it->first,ss = it->second - d[i];
tot -= d[i];
ans += d[i] * (it->first + add);
d[i] = 0;
s.erase(it);
s.insert(pii{val,ss});
break;
}
else {
d[i] -= it->second;
tot -= it->second;
ans += (it->second) * (it->first + add);
it = s.erase(it);
}
}
if(tot > mx[i] && i != n) {
auto it = s.end();
it--;
LL dec = tot - mx[i];
while(1) {
if(it->second <= dec) {
dec -= it->second;
it = s.erase(it);
if(dec == 0) break;
it--;
}
else {
LL val = it->first,ss = it->second - dec;
s.erase(it);
s.insert(pii{val,ss});
break;
}
}
tot = mx[i];
}
}
printf("%lld\n",ans);
}
// system("pause");
return 0;
}
View Code