lock
直接模拟题意，过程略。
#include<bits/stdc++.h>
using namespace std;
int st[15][15];
int dis(int x,int y){
if(x < y)return y - x;
return y + 10 - x;
}
bool match(int a[],int b[]){
int num = 0,s = 0,p = 0;
for(int i = 1;i <= 5;i++)
if(a[i] != b[i]){
if(num == 0){
num++;
s = dis(a[i],b[i]);
p = i;
}
else if(num == 1){
if(i != p + 1)return false;
if(dis(a[i],b[i]) != s)return false;
num++;
}
else return false;
}
return (num == 1 || num == 2);
}
int main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= 5;j++)cin >> st[i][j];
int ans = 0;
for(int i = 0;i <= 99999;i++){
int t = i;int cur[15];
for(int j = 1;j <= 5;j++){cur[j] = t % 10;t /= 10;}
int mat = 0;
for(int j = 1;j <= n;j++)
if(match(cur,st[j]))mat++;
if(mat == n)ans++;
}
cout << ans << '\n';
return 0;
}
game
考虑平方怎么做。拿一个栈来匹配，每次栈顶能消就消，记录一下每个元素匹配的位置，令其为 \(to_i\)，那么一个元素如果没匹配上一定是跳过匹配的一段去匹配，也就是不断地令 \(j = to_j +1\) 直到匹配，算一下深度就是答案。
时间复杂度 \(O(26n)\)，原因是每种字符只会遍历一遍
#include<bits/stdc++.h>
using namespace std;
const int MX = 2e6 + 7;
int n;char s[MX];
int to[MX],dep[MX];
int main(){
cin >> n >> s + 1;
to[n] = n + 1;
long long ans = 0;
for(int i = n - 1;i >= 1;i--){
int j = i + 1;
while(j <= n && s[j] != s[i])j = to[j] + 1;
to[i] = j;
if(to[i] > n)continue;
else{
dep[i] = dep[to[i] + 1] + 1;
ans += dep[i];
}
}
cout << ans << '\n';
return 0;
}
struct
模拟。代码逻辑较为清晰，建议直接看。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pll pair<long long,long long >
#define fir first
#define sec second
const int MX = 1005;
struct Type{
string name;
int shift;
ll sz;
vector<string > itemType,itemName;
vector<ll > itemLpos,itemRpos;
void print(){
cerr << "struct name = " << name << '\n';
cerr << "shift = " << shift << '\n';
cerr << "sz = " << sz << '\n';
for(int i = 0;i < itemType.size();i++){
cerr << itemType[i] << ' ' << itemName[i] << '\n';
cerr << "memory pos : " << itemLpos[i] << ' ' << itemRpos[i] << '\n';
}
}
}st[MX];
int id = 0;
int tot = 3;
map<string,int > nameTable;
void init(){
nameTable["byte"] = 0;
nameTable["short"] = 1;
nameTable["int"] = 2;
nameTable["long"] = 3;
st[0].name = "byte";
st[1].name = "short";
st[2].name = "int";
st[3].name = "long";
st[0].shift = 1,st[0].sz = 1;
st[1].shift = 2,st[1].sz = 2;
st[2].shift = 4,st[2].sz = 4;
st[3].shift = 8,st[3].sz = 8;
}
void opt1(){
string name;int k,maxshift = 0;ll sz = 0;
cin >> name >> k;
vector<string > itTypes,itNames;
for(int i = 1;i <= k;i++){
string itType,itName;
cin >> itType >> itName;
itTypes.push_back(itType);
itNames.push_back(itName);
int id = nameTable[itType];
maxshift = max(maxshift,st[id].shift);
}
int cur = ++tot;ll L = 0,lasSz = 0;
for(int i = 0;i < k;i++){
string itType = itTypes[i],itName = itNames[i];
int id = nameTable[itType];
if(i != 0){
L += lasSz;
while(L % st[id].shift != 0)L++;
}
st[cur].itemType.push_back(itType);
st[cur].itemName.push_back(itName);
st[cur].itemLpos.push_back(L);
st[cur].itemRpos.push_back(L + st[id].sz - 1);
lasSz = st[id].sz;
}
L += lasSz;
while(L % maxshift != 0)L++;
st[cur].shift = maxshift;st[cur].sz = L;
nameTable[name] = cur;
st[cur].name = name;
cout << L << ' ' << maxshift << '\n';
}
struct mem{
ll L,R;
string type,name;
bool operator < (const mem b)const{
return L < b.L;
}
};
mem memBox[MX];
int lasMem = 0,memcnt = 0;
void opt2(){
string type,name;
cin >> type >> name;
int id = nameTable[type];
if(lasMem != 0){
while(lasMem % st[id].shift != 0)lasMem++;
}
cout << lasMem << '\n';
mem newE;
newE.L = lasMem;newE.R = lasMem + st[id].sz - 1;
lasMem = newE.R + 1;
newE.type = type;newE.name = name;
memBox[++memcnt] = newE;
}
void opt3(string ele){
vector<string > div;string tmp = "";
for(int i = 0;i < ele.size();i++){
if(ele[i] == '.'){
div.push_back(tmp);
tmp = "";
}
else tmp += ele[i];
}
div.push_back(tmp);
tmp = "";
int pos = 0,typeId = 0;
for(int i = 1;i <= memcnt;i++){
if(memBox[i].name == div[0]){
pos = i;
typeId = nameTable[memBox[i].type];
}
}
//pos = ele pos
ll dx = memBox[pos].L;
for(int i = 1;i < div.size();i++){
for(int j = 0;j < st[typeId].itemType.size();j++)
if(st[typeId].itemName[j] == div[i]){
dx += st[typeId].itemLpos[j];
typeId = nameTable[st[typeId].itemType[j]];
break;
}
}
cout << dx << '\n';
}
void opt4(){
ll addr,tmpd;
cin >> addr;
tmpd = addr;
int typeId = 0;bool find = false;
vector<string > output;
for(int i = 1;i <= memcnt;i++)
if(memBox[i].L <= addr && addr <= memBox[i].R){
typeId = nameTable[memBox[i].type];
output.push_back(memBox[i].name);
addr -= memBox[i].L;
find = true;
}
if(!find){
cout << "ERR\n";
return;
}
bool flag = true;
for(;;){
if(typeId < 4)break;
bool ok = false;
for(int j = 0;j < st[typeId].itemType.size();j++){
if(st[typeId].itemLpos[j] <= addr && addr <= st[typeId].itemRpos[j]){
addr -= st[typeId].itemLpos[j];
output.push_back(st[typeId].itemName[j]);
typeId = nameTable[st[typeId].itemType[j]];
ok = true;
break;
}
}
if(!ok){
flag = false;
break;
}
}
if(!flag)cout << "ERR\n";
else{
for(int i = 0;i < output.size();i++){
if(i != 0)cout << ".";
cout << output[i];
}
cout << '\n';
}
}
signed main(){
init();
int n;
cin >> n;
for(int i = 1;i <= n;i++){
int opt;
cin >> opt;
if(opt == 1)opt1();
if(opt == 2)opt2();
if(opt == 3){
string tmp;
cin >> tmp;
opt3(tmp);
}
if(opt == 4)opt4();
}
//for(int i = 4;i <= tot;i++)st[i].print();
return 0;
}
tree
考虑先二分答案，对于每个点求出至少要在什么时间踩上去，然后直接贪心，每次去标时间最靠前的节点，时间复杂度 \(O(n\log^2V)\) 至 \(O(n\log V)\)。
我写的 \(O(n\log n\log V)\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
i128 read(){
i128 x = 0,ch = getchar(),f = 1;
while(ch < 48 || ch > 57){
if(ch == '-')f = -1;
ch = getchar();
}
while(ch >= 48 && ch <= 57)x = x * 10 + ch - 48,ch = getchar();
return x * f;
}
const int MX = 1e5 + 7;
int n;
ll a[MX],b[MX],c[MX],t[MX];
vector<int > g[MX];
//b,c,天数为d
i128 calc(ll b,ll c,ll d){
if(c < 0){
ll zero = (1 - b) / c;
if((1 - b) % c == 0)zero--;
i128 ret = 0,d0 = min(d,zero);
ret += (i128)(b + c + b + (i128)d0 * c) * d0 / 2;
ret += d - d0;
return ret;
}
return (i128)(b + c + b + (i128)c * d) * d / 2;
}
//a,b,c的树最晚要啥时候踩上去
int days(ll a,ll b,ll c,int T){
int l = 1,r = min((int)n,T),ans = 0;
i128 tot = calc(b,c,T);
while(l <= r){
int mid = l + r >> 1;
if(tot - calc(b,c,mid - 1) >= a){ans = mid,l = mid + 1;}
else r = mid - 1;
}
return ans;
}
bool vis[MX];int fa[MX];
void dfs(int x,int f){
fa[x] = f;
for(int i = 0;i < g[x].size();i++){
int to = g[x][i];
if(to == f)continue;
dfs(to,x);
}
}
struct st{
int id;
i128 t;
}s[MX];
st mk(int id,i128 t){
st ret;
ret.id = id;ret.t = t;
return ret;
}
vector<st > buc[MX];
bool cmp(st x,st y){return x.t < y.t;}
bool check(int T){
for(int i = 1;i <= n;i++)t[i] = days(a[i],b[i],c[i],T);
//cerr << "cur ending = " << (int)T << '\n';
//cerr << "days : \n";
//for(int i = 1;i <= n;i++)cout << (int)t[i] << ' ';
//cout << '\n';
for(int i = 1;i <= n;i++){buc[i].clear();buc[i].resize(0);}
for(int i = 1;i <= n;i++)
if(t[i] == 0)return false;
else if(t[i] <= n)buc[t[i]].push_back(mk(i,t[i]));
int tot = 0;
for(int i = 0;i <= n;i++)
for(int j = 0;j < buc[i].size();j++)s[++tot] = buc[i][j];
memset(vis,false,sizeof(vis));
int d = 1;
//cerr << "start\n";
for(int k = 1;k <= tot;k++){
int i = s[k].id;
if(vis[i])continue;
vector<int > grand;
grand.push_back(i);
while(fa[i] != 0 && !vis[fa[i]]){
grand.push_back(fa[i]);
i = fa[i];
}
for(int j = grand.size() - 1;j >= 0;j--){
//cerr << "col node " << grand[j] << '\n';
if(t[grand[j]] < d)return false;
vis[grand[j]] = true;
d++;
}
}
return true;
}
int main(){
n = read();
for(int i = 1;i <= n;i++){a[i] = read();b[i] = read();c[i] = read();}
for(int i = 1;i < n;i++){
int u = read();int v = read();
g[u].push_back(v);g[v].push_back(u);
}
//cout << "node 4 : \n";
//for(int i = 1;i <= 6;i++)cout << (int)calc(b[4],c[4],i) << ' ';
//cerr << '\n';
dfs(1,0);
int l = 1,r = 1000000000,ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)){ans = mid,r = mid - 1;}
else l = mid + 1;
}
cout << ans << '\n';
return 0;
}