uva839 （递归来判断天平是否平衡）（递归+树）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
bool solve(int& W){
int w1, l1, w2, l2;
cin>>w1>>l1>>w2>>l2;
bool flag1, flag2;
flag1 = flag2 = true;
if(w1 == 0) flag1 = solve(w1);
if(w2 == 0) flag2 = solve(w2);
W = w1+w2;
if(flag1&&flag2&&w1*l1 == w2*l2) return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
int m;
while(_--){
if(solve(m)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
if(_) cout<<endl;
}
return 0;
}
四分树的递归统计 （分治）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
const int len = 32;
char s[1024+10];
int ans = 0;
bool vis[len][len];
void draw(char *s, int &p, int r, int c, int w){
char ch = s[p++];
if(ch == 'p'){
draw(s, p, r, c+w/2, w/2);
draw(s, p, r, c, w/2);
draw(s, p, r+w/2, c, w/2);
draw(s, p, r+w/2, c+w/2, w/2);
}
else if(ch == 'f'){
for(int i=r; i<r+w; i++){
for(int j=c; j<c+w; j++){
if(!vis[i][j]) {
vis[i][j] = true;
ans++;
}
}
}
}
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cls(vis, 0);
ans = 0;
for(int i=0; i<2; i++){
cin>>s;
int p=0;
draw(s, p, 0, 0, len);
}
cout<<"There are "<<ans<<" black pixels."<<endl;
}
return 0;
}
四分树2
petri网络的模拟（模拟）
一个P节点有若干的资源，一个T(transaction)节点在入节点有足够多的资源之后，会触发事件，并且使出节点的资源增加。问是否是一个循环的网络，若在规定的时间内出现了资源不足的情况，那么该网络就死了。
问最后每一个节点的最后的资源的个数。
我WA了三发就是因为输出的格式有问题。。。
问题本身是一个相对简单的模拟，按照顺序模拟就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 100+10;
int NP, NT;
int token[maxn];
struct Node{
bool in[maxn], out[maxn];
//vector<int> iid, oid;
int din[maxn], dout[maxn];
}node[maxn];
int main(){
ios::sync_with_stdio(false);
int kase=1;
while(~scanf("%d", &NP)&&NP){
for(int i=1; i<=NP; i++) scanf("%d", &token[i]);
scanf("%d", &NT);
for(int i=1; i<=NT; i++){
cls(node[i].in, 0), cls(node[i].out, 0);
//node[i].iid.clear(), node[i].oid.clear();
cls(node[i].din, 0), cls(node[i].dout, 0);
}
for(int i=1; i<=NT; i++){
int id;
while(scanf("%d", &id)&&id){
if(id<0){
node[i].in[-id] = true, node[i].din[-id]++;
}
else node[i].out[id]=true, node[i].dout[id]++;
}
}
int cnt = 0;
int lim;
scanf("%d", &lim);
for(int i=1; i<=NT; i++){
bool trig = true;
for(int j=1; j<=NP; j++){
if(node[i].in[j]&&node[i].din[j]>token[j]){
trig = false;
break;
}
}
if(!trig) continue;
for(int j=1; j<=NP; j++){
token[j] -= node[i].din[j];
token[j] += node[i].dout[j];
}
i=0;
cnt++;
if(cnt>=lim) break;
}
if(cnt>=lim){
printf("Case %d: still live after %d transitions
", kase++, lim);
}
else{
printf("Case %d: dead after %d transitions
", kase++, cnt);
}
printf("Places with tokens:");
for(int i=1;i<=NP;++i) if(token[i]) printf(" %d (%d)",i,token[i]);
printf("
");
}
return 0;
}
列车调度 （栈）
栈的模拟，uva的输入格式真的很奇葩
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int n;
stack<int> s;
int target[maxn];
int main(){
ios::sync_with_stdio(false);
while(cin>>n&&n){
while(true){
cin>>target[1];
if(target[1] == 0) {
cout<<endl;
break;
}
for(int i=2; i<=n; i++) cin>>target[i];
while(!s.empty()) s.pop();
int A, B;
A = B = 1;
bool ok = true;
while(B<=n){
if(A == target[B]) A++, B++;
else if(!s.empty()&&target[B] == s.top()) B++, s.pop();
else if(A<=n) s.push(A), A++;
else {
ok = false;
break;
}
}
if(ok) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
矩阵的乘法 （栈）
这道题比较特殊的一点就是任何两个矩阵之间都会有括号，这样就会导致最后的stack里面只有一个结果矩阵。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
struct Matrix{
int a, b;
}node[maxn];
int n;
int main(){
ios::sync_with_stdio(false);
cin>>n;
string name;
int x, y;
for(int i=1; i<=n; i++){
cin>>name>>x>>y;
node[name[0]-'A'].a = x;
node[name[0]-'A'].b = y;
}
string op;
stack<Matrix> s;
while(cin>>op){
bool flag = false;
int ans = 0;
for(int i=0; i<op.length(); i++){
if(op[i]>='A'&&op[i]<='Z') s.push(node[op[i]-'A']);
else if(op[i] ==')'){
Matrix m2 = s.top();s.pop();
Matrix m1 = s.top();s.pop();
if(m1.b!=m2.a){
flag = true;
break;
}
ans += m1.a*m2.a*m2.b;
s.push(Matrix{m1.a, m2.b});
}
}
if(flag){
cout<<"error"<<endl;
}
else cout<<ans<<endl;
}
return 0;
}
flip （规律）
注意数组不是一个排列！，每次都选择数组中的最大的数进行操作。
lrj输入输出混用了。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include <sstream>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 30+10;
int n, a[maxn];
void flip(int p){
for(int i=0; i<p-i; i++){
swap(a[i], a[p-i]);
}
cout<<n-p<<" ";
}
int main(){
ios::sync_with_stdio(false);
string s;
while(getline(cin, s)){
cout<<s<<endl;
n=0;
stringstream ss(s);
while(ss>>a[n]) n++;
//cout<<n<<endl;
for(int i=n-1; i>=0; i--){
int pos = max_element(a, a+i+1)-a;
//cout<<pos<<endl;
if(pos == i) continue;
if(pos>0) flip(pos);//将最大的翻上去
//将最大的翻到最底
flip(i);
}
cout<<0<<endl;
}
return 0;
}
uva1471 （数据结构优化dp）
删去连续的一段，使得剩下的序列中，一段连续的增序列的长度最长。
set的lower_bound()的灵活的运用。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
struct Node{
int val,g;
bool operator < (const Node &b) const{
return val<b.val;
}
};
int a[maxn];
int n;
set<Node> s;
int g[maxn], f[maxn];
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
}
g[1] = 1, f[n] = 1;
s.clear();
for(int i=2; i<=n; i++){
if(a[i-1]<a[i]) g[i] = g[i-1]+1;
else g[i] = 1;
}
for(int i=n-1; i>=1; i--){
if(a[i+1]>a[i]) f[i] = f[i+1]+1;
else f[i] = 1;
}
s.insert(Node{a[1], g[1]});
int ans = 1;
for(int i=2; i<=n; i++){
Node now = Node{a[i], g[i]};
set<Node>::iterator it = s. lower_bound(now);
bool have = true;
if(it!=s.begin()){
Node last = *(--it);
ans = max(ans, last.g+f[i]);
if(g[i]<=last.g) have=false;
}
if(have){
s.erase(now);
s.insert(now);
it = s. upper_bound(now);
while(it!=s.end()&&it->g<=now.g) s.erase(it++);
}
}
cout<<ans<<endl;
}
return 0;
}
理想路径 (最小字典序+bfs)
有n个点m条边的无向图，每条边有一个颜色。
问1->n的最短路的颜色最小字典序。
两遍bfs:
- 第一遍求出各个点到n节点的最短路，其实可以顺着做，也可以逆着做。
- 从1节点出发，不断的试探最小的颜色，就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int n, m;
struct Node{
int v, c;
};
vector<Node> G[maxn];
bool vis[maxn];
int d[maxn];
void rev_bfs(){
cls(vis, 0);
cls(d, 0x3f);
queue<int> q;
q.push(n);
vis[n] = true;
d[n] = 0;
while(!q.empty()){
int v = q.front();
q.pop();
for(int i=0; i<G[v].size(); i++){
int u = G[v][i].v;
if(!vis[u]&&d[u]>d[v]+1){
vis[u] = true;
d[u] = d[v]+1;
q.push(u);
}
}
}
}
vector<int> ans;
void bfs(){
cls(vis, 0);
vector<int> next, next2;
ans.clear();
next.push_back(1);
vis[1] = true;
for(int i=0; i<d[1]; i++){
int minc = inf;
for(int j=0; j<next.size(); j++){
int u = next[j];
for(int k=0; k<G[u].size(); k++){
int v = G[u][k].v;
int c = G[u][k].c;
if(!vis[v] && d[u] == d[v]+1){
minc = min(minc, c);
}
}
}
ans.push_back(minc);
next2.clear();
for(int j=0; j<next.size(); j++){
int u = next[j];
for(int k=0; k<G[u].size(); k++){
int v = G[u][k].v;
int c = G[u][k].c;
if(!vis[v] && d[u] == d[v]+1&&c == minc){
vis[v] = true;
next2.push_back(v);
}
}
}
next = next2;
}
cout<<ans.size()<<endl;
for(int i=0; i<ans.size()-1; i++){
cout<<ans[i]<<" ";
}
cout<<ans[ans.size()-1]<<endl;
}
int main(){
ios::sync_with_stdio(false);
while(cin>>n>>m){
int u, v, c;
for(int i=1; i<=n; i++) G[i].clear();
for(int i=0; i<m; i++){
cin>>u>>v>>c;
G[u].push_back(Node{v, c});
G[v].push_back(Node{u, c});
}
rev_bfs();
bfs();
}
return 0;
}
抄书(二分+贪心)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 500+10;
int a[maxn];
int n, m;
bool check(int mid){
int tot = 0 ;
int cnt = 0;
for(int i=n; i>=1; i--){
if(a[i]>mid){
return false;
}
if(tot+a[i]<=mid){
tot += a[i];
}
else{
cnt++;
tot = a[i];
}
}
if(tot>0){
tot = 0;
cnt++;
}
return cnt<=m;
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
int l=0, r = 1e9;
int ans = 0;
while(l<r){
int mid = l+(r-l)/2;
if(check(mid)){
ans = mid;
r=mid;
}
else l=mid+1;
}
int sum = 0;
bool in[maxn];
cls(in, 0);
//cout<<ans<<endl;
for(int i=n; i>=1; i--){
if(i<=m-1){
in[i] = true;
m--;
continue;
}
if(sum +a[i]<=ans){
sum += a[i];
}
else{
sum = a[i];
in[i] = true;
m--;
}
}
for(int i=1; i<n; i++){
cout<<a[i];
if(in[i]){
cout<<" / ";
}
else cout<<" ";
}
cout<<a[n]<<endl;
}
return 0;
}
uva1442 洞窟 （扫两遍）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
int d[maxn];
int t[maxn];
int h[maxn];
int n;
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>n;
for(int i=1; i<=n; i++)cin>>d[i];
for(int i=1; i<=n; i++)cin>>t[i];
int level = t[1];
for(int i=1; i<=n; i++){
if(d[i]>level) level = d[i];
if(level>t[i]) level = t[i];
h[i] = level;
}
int ans = 0;
level = t[n];
for(int i=n; i>=1; i--){
if(d[i]>level) level = d[i];
if(level>t[i]) level = t[i];
ans += min(h[i], level)-d[i];
}
cout<<ans<<endl;
}
return 0;
}
uva 1354 mobile computing (枚举二叉树)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 6+10;
int w[maxn];
int sum[1<<6];
int n;
double R;
struct Node{
double l, r;
};
vector<Node> node[1<<6];
bool vis[1<<6];
void dfs(int x){
if(vis[x]) return;
vis[x] = true;
bool has_child = false;
//cout<<x<<endl;
for(int l=(x-1)&x; l; l=(l-1)&x){
int r = x^l;
has_child = true;
double d1 = 1.0*sum[r]/sum[x];
double d2 = 1.0*sum[l]/sum[x];
dfs(l), dfs(r);
for(int i=0; i<node[l].size(); i++){
for(int j=0; j<node[r].size(); j++){
Node temp = Node{0, 0};
temp.l = max(node[l][i].l+d1, node[r][j].l-d2);
temp.r = max(node[r][j].r+d2, node[l][i].r-d1);
//cout<<temp.l<<" "<<temp.r<<endl;
if(temp.l+temp.r<=R) node[x].push_back(temp);
}
}
}
if(!has_child) node[x].push_back(Node{0, 0});
}
int main(){
ios::sync_with_stdio(false);
int _;
cin>>_;
while(_--){
cin>>R>>n;
for(int i=0; i<n; i++) cin>>w[i];
for(int i=1; i<(1<<n); i++){
sum[i] = 0;
node[i].clear();
for(int j=0; j<n; j++) if(i&(1<<j)) sum[i]+=w[j];
}
cls(vis, 0);
dfs((1<<n)-1);
double ans = -1;
for(int i=0; i<node[(1<<n)-1].size(); i++){
ans = max(ans, node[(1<<n)-1][i].l+node[(1<<n)-1][i].r);
}
if(ans == -1){
cout<<-1<<endl;
}
else{
cout<<fixed<<setprecision(11);
cout<<ans<<endl;
}
}
return 0;
}