文章目录
2018-2019 ACM-ICPC, Asia Seoul Regional Contest
A Circuits
扫描线+线段树
const int maxn = 3e5+10;
vector<int> beg[maxn],en[maxn];
int a[maxn],b[maxn];// b用于离散化
int y[maxn][2];
#define lson (o<<1)
#define rson (o<<1|1)
LL sum[maxn<<2],add[maxn<<2],_max[maxn<<2];
void pushdown(int o,int l,int r){
if(add[o]){
add[lson] += add[o];
add[rson] += add[o];
_max[lson] += add[o];
_max[rson] += add[o];
add[o] = 0;
}
}
void pushup(int o,int l,int r){
_max[o] = max(_max[lson],_max[rson]);//+add[o];
}
void update(int o,int l,int r,int L,int R,int p){
if(L <= l && r <= R) {
add[o] += p;
_max[o] += p;
return ;
}
pushdown(o,l,r);
int m = (l+r)>>1;
if(L <= m)
update(lson,l,m,L,R,p);
if(R > m)
update(rson,m+1,r,L,R,p);
pushup(o,l,r);
}
LL _T = 0;
void query(int o,int l,int r,int L,int R){
if(L <= l && R >= r){
_T = max(_T,_max[o]);
return ;
}
pushdown(o,l,r);
int m = (l+r)>>1;
if(L <= m)
query(lson,l,m,L,R);
if(R > m)
query(rson,m+1,r,L,R);
}
int tmp[maxn];
int main(void)
{
int n;cin>>n;
int cnt = 0;
for(int i = 1; i <= n; ++i){
int aa,bb;scanf("%d%d%d%d",&aa,&y[i][1],&bb,&y[i][0]);
a[++cnt] = y[i][0];
a[++cnt] = y[i][1];
}
memcpy(b,a,sizeof(b));
sort(b+1,b+cnt+1);
int tot = unique(b+1,b+cnt+1)-(b+1);
cnt = tot;
for(int i = 1;i <= n; ++i){
y[i][0] = lower_bound(b+1,b+tot+1,y[i][0])-b;
y[i][1] = lower_bound(b+1,b+tot+1,y[i][1])-b;
beg[y[i][0]].push_back(i);
en[y[i][1]].push_back(i);
update(1,1,tot,y[i][0],y[i][1],1);
}
for(int i = 1;i <= tot; ++i)
{
_T = 0;
query(1,1,tot,i,i);
tmp[i] = _T;
}
LL ans = 0;
for(int i = 1;i <= tot; ++i){
for(auto j: beg[i])
update(1,1,tot,y[j][0],y[j][1],-1);
_T = 0;
query(1,1,tot,1,tot);
ans = max(ans,tmp[i]+_T);
for(auto j: en[i])
update(1,1,tot,y[j][0],y[j][1],1);
}
cout<<ans<<endl;
return 0;
}
B Cosmetic Survey
按照题目要求建好边好直接跑floyd 就ok了
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500+10;
const int INF = 1e8;
int d[maxn][maxn];
int ar[maxn][maxn];
int n,m;
int s[maxn][maxn];
int main(void){
cin>>m>>n;
for(int i = 1;i <= n; ++i){
for(int j = 1;j <= m; ++j){
scanf("%d",&ar[i][j]);
if(ar[i][j] == 0)
ar[i][j] = INF;
}
}
for(int i = 1;i <= m; ++i){
for(int j = i+1;j <= m; ++j){
if(i == j) continue;
for(int k = 1; k <= n; ++k){
if(ar[k][i] < ar[k][j])
d[i][j]++;
else if(ar[k][i] > ar[k][j])
d[j][i]++;
}
int x = d[i][j],y = d[j][i];
if(x >= y)
d[j][i] = 0;
if(x <= y)
d[i][j] = 0;
}
}
// for(int i = 1;i <= m; ++i,cout<<endl)
// for(int j = 1;j <= m; ++j)
// cout<<d[i][j]<<" ";
for(int k = 1;k <= m; ++k){
for(int i = 1;i <= m; ++i){
for(int j = 1;j <= m; ++j){
if(d[i][k] == 0 || d[k][j] == 0) continue;
d[i][j] = max(d[i][j],min(d[i][k],d[k][j]));
}
}
}
// for(int i = 1;i <= m; ++i,cout<<endl)
// for(int j = 1;j <= m; ++j)
// cout<<d[i][j]<<" ";
vector<int> ans;
for(int i = 1;i <= m; ++i){
bool yes = true;
for(int j = 1;j <= m; ++j){
if(i == j) continue;
if(d[i][j] < d[j][i])
yes = false;
}
if(yes)
ans.push_back(i);
}
for(int i = 0;i < ans.size(); ++i)
printf("%d%c",ans[i]," \n"[i==ans.size()-1]);
return 0;
}
D Go Latin
基本的字符串处理，队友用正则切了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
string s;
const int cnt = 12;
string src[] = {"a$","i$","y$","l$","n$","ne$","o$","r$","t$","u$","v$","w$"};
string dst[] = {"as", "ios", "ios", "les", "anes", "anes", "os", "res", "tas", "us", "ves", "was"};
int main(){
cin >> n;
for (int i=0; i<n; ++i) {
cin >> s;
for (int i=0; i<cnt; ++i) {
regex reg(src[i]);
if (regex_search(s,reg)) {
cout << regex_replace(s,reg,dst[i]) << endl;
goto nex;
}
}
cout << s << "us\n";
nex:;
}
return 0;
}
F Parentheses
字符串大模拟
感谢队友！
#include <bits/stdc++.h>
//F
using namespace std;
typedef long long ll;
typedef long long LL;
map<char, bool> optdic;
string str, s;
inline bool isopt(char ch)
{
return optdic.count(ch);
}
bool iserror()
{
for (int i = 1; i < s.size(); i++)
{
if (isalpha(s[i]) && isalpha(s[i - 1]))
{
return true;
}
if (isopt(s[i]) && isopt(s[i - 1]))
{
return true;
}
if (s[i] == ')' && s[i - 1] == '(')
{
return true;
}
if (isopt(s[i]) && s[i - 1] == '(')
{
return true;
}
if (s[i] == ')' && isopt(s[i - 1]))
{
return true;
}
}
int lef = 1;
for (int i = 1; i < s.size(); i++)
{
if (s[i] == '(')
{
lef++;
}
if (s[i] == ')')
{
lef--;
if (lef < 0 || (lef == 0 && i != s.size() - 1)) return true;
}
}
if (lef) return true;
return false;
}
bool issubproper(int p)
{
int con = 0, i = p + 1;
for (; s[i] != ')'; i++)
{
if (isopt(s[i])) con++;
if (s[i] == '(')
{
if (!issubproper(i)) return false;
}
s[i] = ' ';
}
s[i] = ' ';
//cout<<endl<<s<<" "<<con<<endl;
if (con != 1) return false;
return true;
}
void initopt()
{
optdic['+'] = optdic['-'] = optdic['*'] = optdic['/'] = optdic['%'] = true;
//optdic['('] = optdic[')'] = true;
}
int main()
{
initopt();
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
getline(cin, str);
s = "(";
for (int i = 0; i < str.size(); i++)
{
if (str[i] != ' ')
{
s += str[i];
}
}
s += ")";
if (iserror()) return 0 * puts("error");
if (issubproper(0)) return 0 * puts("proper");
return 0 * puts("improper");
}
京公网安备 11010502036488号