A、田地丈量
样例输入1
4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15
44
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
#define x1 asdawd
#define y1 hjhjkhf
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n;
int a, b;
int x1, y1, x2, y2;
int main(){
// freopen("hh.txt", "r", stdin);
read(n), read(a), read(b);
ll ans = 0;
for(int i = 1; i <= n; i++){
cin >> x1 >> y1 >> x2 >> y2;
if(x2 < 0 || x1 > a || y2 < 0 || y1 > b) continue;
int mx1 = min(x2, a);
int my1 = min(y2, b);
int mx2 = max(0, x1);
int my2 = max(0, y1);
ans += (mx1 - mx2) * (my1 - my2);
}
cout << ans << endl;
return 0;
}
B、垦田计划
样例输入2
4 9 2
6 1
5 1
6 2
7 1
5
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int n, m, k;
int t[N], c[N];
bool check(int lim){
int m1 = m;
for(int i = 1; i <= n; i++){
if(k > lim) return 0;
if(t[i] > lim){
int del = t[i] - lim;
m1 -= c[i] * del;
}
}
return m1 >= 0;
}
int main(){
// freopen("hh.txt", "r", stdin);
read(n), read(m), read(k);
for(int i = 1; i <= n; i++){
read(t[i]), read(c[i]);
}
int l = 1, r = 1e9;
int ans = 0;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << endl;
return 0;
}
C、LDAP
测试样例3
2
1 2 1 2 2 3
2 2 2 3 3 1
4
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)
1
1
1 2
#include <bits/stdc++.h>
using namespace std;
#define N 2500
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
struct People{
int DN; // 题目中编号
map <int, int> G;
} p[N];
int n, m;
set <int> ans;
struct node{
int op; // 1表示 |, 2表示 &
int lson, rson;
int left; int right;
int op1; // 1表示 :, 2表示 ~
void clean(){
op = op1 = -1;
lson = 0, rson = 0;
left = 0, right = 0;
return ;
}
void print(){
printf("%d %d %d %d %d %d\n", op, lson, rson, op1, left, right);
return ;
}
node(){
op = -1;
op1 = -1;
return ;
}
} t[N];
int id = 0;
int dfn = 0; // 当前节点编号
string s;
int root = 0;
void clean(){ // 清空树
for(int i = 0; i <= dfn; i++)
t[i].clean();
return ;
}
void dfs(int &now){
now = ++dfn;
if(id >= s.length()) return ;
if(s[id] == '|' || s[id] == '&'){ // 这个点是逻辑符编号
t[now].op = s[id] == '|' ? 1 : 2;
id += 2; // 越过左括号
dfs(t[now].lson);
dfs(t[now].rson);
}
else if(isdigit(s[id])){ // 表达式
int tmp = 0;
while(isdigit(s[id])){
tmp = tmp * 10 + (s[id] - '0');
id++;
}
t[now].left = tmp;
t[now].op1 = s[id] == ':' ? 1 : 2;
tmp = 0;
id++;
while(isdigit(s[id])){
tmp = tmp * 10 + (s[id] - '0');
id++;
}
t[now].right = tmp;
while(s[id] == '(' || s[id] == ')') id++;
return ;
}
return ;
}
int get_ans(int now, int pid){ // pid: 检查 pid 是否符合这一条的要求
// printf("now: %d\n", now);
// t[now].print();
if(t[now].op != -1){ // 这一个点是逻辑符
if(t[now].op == 1) return get_ans(t[now].lson, pid) | get_ans(t[now].rson, pid);
else return get_ans(t[now].lson, pid) & get_ans(t[now].rson, pid);
}
else{ // 这一个节点是运算
int left = t[now].left, right = t[now].right;
int op1 = t[now].op1;
bool flag = 0;
if(op1 == 1){
if(p[pid].G.count(left) && p[pid].G[left] == right) flag = 1;
}
else{
if(p[pid].G.count(left) && p[pid].G[left] != right) flag = 1;
}
return flag;
}
}
void check(){
id = 0; // 第 0 位开始检查 s
dfn = 0;
root = 0;
dfs(root); // 建树
for(int i = 1; i <= n; i++){
int tmp = get_ans(root, i);
if(tmp) ans.insert(p[i].DN);
}
return ;
}
int main(){
// freopen("hh.txt", "r", stdin);
read(n);
for(int i = 1; i <= n; i++){
read(p[i].DN);
int num; read(num);
for(int j = 1; j <= num; j++){
int x, y;
read(x), read(y);
p[i].G[x] = y;
}
}
read(m);
for(int i = 1; i <= m; i++){
ans.clear();
cin >> s;
clean();
check();
for(auto it : ans){
printf("%d ", it);
}
puts("");
}
return 0;
}