1063 Set Similarity
n个序列分别先放进集合里去重。在询问的时候，遍历A集合中每个数，判断下该数在B集合中是否存在，统计存在个数（分子），分母就是两个集合大小减去分子。
// 1063 Set Similarity
#include <set>
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; set <int> se[]; int main() {
int n, k, m;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &m);
while(m--) {
scanf("%d", &k);
se[i].insert(k);
}
}
scanf("%d", &k);
while(k--) {
int id1, id2;
double cnt = , total = ;
scanf("%d %d", &id1, &id2);
for(int i : se[id1]) {
if(se[id2].find(i) != se[id2].end()) cnt++;
}
total = se[id1].size() + se[id2].size() - cnt;
printf("%.1f%\n", cnt * / total);
}
return ;
}
1064 Complete Binary Search Tree
按照中序遍历建树。对应根节点依次填入排序好的数即可。
// 1064 Complete Binary Search Tree
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int a[N], level[N], n, cnt = ; void solve(int root) {
if(root > n) return ;
solve( * root);
level[root] = a[++cnt];
solve( * root + );
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
sort(a + , a + + n);
solve();
for(int i = ; i <= n; i++) {
if(i != ) printf(" ");
printf("%d", level[i]);
}
return ;
}
1065 A+B and C (64bit)
对溢出的情况特判一下。
// 1065 A+B and C (64bit)
#include <iostream>
using namespace std; typedef long long ll; int main() {
int t;
scanf("%d", &t);
for(int i = ; i <= t; i++) {
ll a, b, c, sum = ;
scanf("%lld %lld %lld", &a, &b, &c);
sum = a + b;
if(a > && b > && sum <= ) {
printf("Case #%d: true\n", i);
} else if(a < && b < && sum >= ) {
printf("Case #%d: false\n", i);
} else if(sum > c) {
printf("Case #%d: true\n", i);
} else {
printf("Case #%d: false\n", i);
}
}
return ;
}
1066 Root of AVL Tree
AVL模板题
#include <bits/stdc++.h>
using namespace std; typedef struct node;
typedef node * tree; struct node{
int v, heigh;
tree L,R;
}; int getheigh(tree root){
if(root==NULL) return ;
return root->heigh;
} void updataheigh(tree root){
root->heigh=max(getheigh(root->L),getheigh(root->R))+;
} int getBalance(tree root){
return getheigh(root->L)-getheigh(root->R);
} void L(tree &root){
tree temp;
temp=root->R;
root->R=temp->L;
temp->L=root;
updataheigh(root);
updataheigh(temp);
root=temp;
} void R(tree &root){
tree temp;
temp=root->L;
root->L=temp->R;
temp->R=root;
updataheigh(root);
updataheigh(temp);
root=temp;
} void insertt(tree &root,int v){
if(root==NULL){
root=new node;
root->v=v;
root->heigh=;
root->L=root->R=NULL;
return;
}
if(v<root->v){
insertt(root->L,v);
updataheigh(root);
if(getBalance(root)==){
if(getBalance(root->L)==){
R(root);
}
else if(getBalance(root->L)==-){
L(root->L);
R(root);
}
}
}
else{
insertt(root->R,v);
updataheigh(root);
if(getBalance(root)==-){
if(getBalance(root->R)==-){
L(root);
}
else if(getBalance(root->R)==){
R(root->R);
L(root);
}
}
} } int main(){
int n;
scanf("%d",&n);
int x;
tree root;
root=NULL;
for(int i=;i<n;i++){
scanf("%d",&x);
insertt(root,x);
}
printf("%d\n",root->v);
return ;
}
1067 Sort with Swap(0, i)
看到表排序的知识，摘录下。
表排序思想：N个数字的排列由若干个独立的环组成
分成以下三种环：
1. 环内只有一个元素，即该数已经在正确的位置上，不需要交换。
2. 环内有 n 个元素，含 0，需要交换次数是：n-1 （每一个非 0 元素都要和 0 换一下）
3. 环内有 n 个元素，不含 0，需要交换的次数是：n+1（把 0 换入换出 + 其余 n-1 个非 0 元素和 0 换一下）
// 1067 Sort with Swap(0, i)
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
bool vis[N];
int pos[N]; int main() {
int n, u, ans = ;
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &u);
pos[u] = i;
}
for(int i = ; i < n; i++) {
if(pos[i] != i && !vis[i]) {
int cnt = , j = i;
do {
cnt++;
vis[j] = true;
if(j == ) cnt -= ;
j = pos[j];
}while(j != i);
cnt++;
ans += cnt;
}
}
printf("%d\n", ans);
return ;
}
1068 Find More Coins
因题目特殊的输出要求，用01背包的时候需要先用大的数填，不然如果先用小的数填，小的数会影响后面的数，最后从小的往大的拿出去即可。
// 1068 Find More Coins
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
int n, m;
int a[N], dp[N];
vector <int> ans;
bool check[N][]; int main() {
scanf("%d %d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
sort(a + , a + + n);
for(int i = n; i >= ; i--) {
for(int j = m; j >= a[i]; j--) {
if(dp[j - a[i]] + a[i] >= dp[j]) {
dp[j] = dp[j - a[i]] + a[i];
check[i][j] = ;
}
}
}
if(dp[m] != m) {
printf("No Solution\n");
return ;
}
int id = ;
while(m > ) {
if(check[id][m]) {
ans.push_back(a[id]);
m -= a[id];
}
id++;
}
for(int i = ; i < ans.size(); i++) {
if(i != ) printf(" ", ans[i]);
printf("%d", ans[i]);
}
return ;
}
1069 The Black Hole of Numbers
按题目模拟即可。
// 1069 The Black Hole of Numbers
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; int a[];
bool cmp(int a, int b) {return a > b;} int cal1(int n) {
memset(a, , sizeof(a));
int cnt = , res = ;
while(n) {
a[++cnt] = n % ;
n /= ;
}
sort(a + , a + + );
for(int i = ; i >= ; i--) {
res = res * + a[i];
}
return res;
} int cal2() {
int res = ;
sort(a + , a + + );
for(int i = ; i <= ; i++) {
res = res * + a[i];
}
return res; } int main() {
int n;
scanf("%d", &n);
while() {
int p1 = cal1(n);
int p2 = cal2();
n = p1 - p2;
printf("%04d - %04d = %04d\n", p1, p2, n);
if(n == || n == ) return ;
}
return ;
}
1070 Mooncake
按每吨多少钱从大到小排序下，再取即可。
// 1070 Mooncake
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ; struct node{
double storage, price;
}moon[N]; bool cmp(node x, node y) {
return x.price * y.storage > y.price * x.storage;
} int main() {
int n;
double d, ans = ;
scanf("%d %lf", &n, &d);
for(int i = ; i <= n; i++) scanf("%lf", &moon[i].storage);
for(int i = ; i <= n; i++) scanf("%lf", &moon[i].price);
sort(moon + , moon + + n, cmp);
for(int i = ; i <= n; i++) {
if(d >= moon[i].storage) {
ans += moon[i].price;
d -= moon[i].storage;
} else {
ans += moon[i].price * (1.0 * d / moon[i].storage);
break;
}
}
printf("%.2f\n", ans);
return ;
}
1071 Speech Patterns
用map存下。更新答案即可。
// 1071 Speech Patterns
#include <map>
#include <string>
#include <iostream>
using namespace std; string in, tmp, ans1;
map<string, int> mp;
map<string, int>::iterator it; int main(){
int ans2 = ;
getline(cin, in);
for(int i = ; i < in.size(); i++) {
if(isalnum(in[i])) {
tmp += tolower(in[i]);
if(i == in.size() - ) mp[tmp]++;
} else {
if(tmp.size()) mp[tmp]++;
tmp.clear();
}
}
for(it = mp.begin(); it!=mp.end(); it++){
if(ans2 < it->second){
ans2 = it -> second;
ans1 = it -> first;
}else if(ans2 == it -> second && ans1 > it -> first){
ans1 = it -> first;
}
}
cout << ans1 << " " << ans2 << endl;
}
1072 Gas Station
以加油站为起点，跑最短路即可。
//1072 Gas Station
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N=1e3+;
const int INF=0x3f3f3f3f;;
int n,m,k,ds,mp[N][N],dis[N],vis[N]; int toint(char s[]){
int sum=;
int len=strlen(s);
for(int i=;i<len;i++){
if(s[i]=='G') continue;
sum=sum*+s[i]-'';
}
if(s[]=='G') return sum+n;
return sum;
} void Dijkstra(int v){
fill(vis,vis+N,false);
fill(dis,dis+N,INF);
for(int i=;i<=n+m;i++) dis[i]=mp[v][i];
dis[v]=;
for(int i=;i<n+m;i++){
int u=-,minn=INF;
for(int j=;j<=n+m;j++){
if(!vis[j]&&minn>dis[j]){
u=j;minn=dis[j];
}
}
vis[u]=true;
for(int j=;j<=n+m;j++){
if(!vis[j]&&dis[j]>mp[u][j]+dis[u]){
dis[j]=mp[u][j]+dis[u];
}
}
}
}
int main(){
int num,a,b;
char s1[],s2[];
scanf("%d %d %d %d",&n,&m,&k,&ds);
fill(mp[],mp[]+N*N,INF);
for(int i=;i<k;i++){
scanf("%s %s %d",s1,s2,&num);
a=toint(s1),b=toint(s2);
mp[a][b]=mp[b][a]=num;
}
int id=-;
double maxDis=-,minAvg=INF;
for(int i=n+;i<=n+m;i++){
Dijkstra(i);
double avg=;
double Min=INF;
bool flag=false;
for(int j=;j<=n;j++){
if(dis[j]>ds){
flag=true;
break;
}
if(Min>dis[j]){
Min=dis[j];
}
avg+=1.0*dis[j]/n;
}
if(flag) continue;
if(maxDis<Min){
maxDis=Min;
id=i;
minAvg=avg;
}
else if(maxDis==Min&&minAvg>avg){
id=i;
minAvg=avg;
} }
if(id==-) printf("No Solution\n");
else{
printf("G%d\n",id-n);
printf("%.1f %.1f\n",maxDis,minAvg);
}
return ;
}
1073 Scientific Notation
按题意模拟即可。
// 1073 Scientific Notation
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
char s[N]; int main() {
int n, i = ;
scanf("%s", s);
n = strlen(s);
while(s[i] != 'E') {
i++;
}
i++;
if(s[] != '+') printf("%c", s[]);
int m = ;
for(int j = i + ; j < n; j++) m = * m + (s[j] - '');
if(s[i] == '+') {
m+=;
for(int j = ; j < i - ; j++) {
m--;
if(m == -) printf(".");
if(s[j] != '.') printf("%c", s[j]);
}
while(m > ) {
printf("");
m--;
}
} else {
m--;
printf("0.");
while(m > ) {
printf("");
m--;
}
for(int j = ; j < i - ; j++) {
if(s[j] != '.') printf("%c", s[j]);
}
}
return ;
}
1074 Reversing Linked List
每k个长度翻转一次。$j$位置对应交换的位置为$(2 * i + k - j - 1)$，这个只使用前半和后半交换，注意特判跳出。
//1074 Reversing Linked List
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int nxt[N], val[N], res[N]; int main() {
int root, n, k, cnt = ;
scanf("%d%d%d", &root, &n, &k);
for(int i = ; i <= n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
val[u] = v; nxt[u] = w;
}
while(root != -) {
res[cnt++] = root;
root = nxt[root];
}
for(int i = ; i + k <= cnt; i += k) {
for(int j = i; j < (i + k); j++) {
if(j >= ( * i + k - j - )) break;
swap(res[( * i + k - j - )], res[j]);
}
}
for(int i = ; i < cnt - ; i++) {
printf("%05d %d %05d\n", res[i], val[res[i]], res[i + ]);
}
printf("%05d %d -1\n", res[cnt - ], val[res[cnt - ]]);
return ;
}
1075 PAT Judge
结构体排序，注意一下区别提交得0分和提交没有通过编译。
// 1075 PAT Judge
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int v[];
int n, k, m;
struct node{
int q[], id, sum, ok, perfect;
}p[N]; void init() {
for(int i = ; i <= n; i++)
for(int j = ; j <= k; j++)
p[i].q[j] = -, p[i].id = i;
} bool cmp(node x, node y) {
if(x.sum == y.sum) {
if(x.perfect == y.perfect) return x.id < y.id;
return x.perfect > y.perfect;
}
return x.sum > y.sum;
} int main() {
int r = ;
scanf("%d %d %d", &n, &k, &m);
for(int i = ; i <= k; i++) scanf("%d", &v[i]);
init();
for(int i = ; i <= m; i++) {
int uid, pid, val;
scanf("%d %d", &uid, &pid);
scanf("%d", &val);
p[uid].q[pid] = max(p[uid].q[pid], val);
}
for(int i = ; i <= n; i++) {
int cnt = , perfect = ;
bool ok = ;
for(int j = ; j <= k; j++) {
if(p[i].q[j] != - && p[i].q[j] != -) cnt += p[i].q[j], ok = ;
if(p[i].q[j] == v[j]) perfect++;
}
if(ok) p[i].ok = ;
else p[i].ok = ;
p[i].sum = cnt;
p[i].perfect = perfect;
}
sort(p + , p + + n, cmp);
for(int i = ; i <= n; i++) {
if(p[i].ok == ) continue;
if(p[i].sum != p[i - ].sum) r = i;
printf("%d %05d %d", r, p[i].id, p[i].sum);
for(int j = ; j <= k; j++) {
if(p[i].q[j] == -) printf(" -");
else if(p[i].q[j] == -) printf("");
else printf(" %d",p[i].q[j]);
}
printf("\n");
}
return ;
}
1076 Forwards on Weibo
DFS或BFS，DFS的时候注意剪枝。
DFS版本
//1076 Forwards on Weibo
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
vector <int> E[N];
bool vis[N];
int layer[N];
int n, m, k, u, sz, ans; void dfs(int u, int l) {
vis[u] = ;
layer[u] = l;
if(l <= k) {
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i];
if(!vis[v] || layer[v] > l + ) {
dfs(v, l + );
}
}
}
} int main() {
scanf("%d %d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &sz);
while(sz) {
sz--;
scanf("%d", &u);
E[u].push_back(i);
}
}
scanf("%d", &m);
while(m--) {
for(int i = ; i <= n; i++) vis[i] = , layer[i] = ;
scanf("%d", &u);
ans = ;
dfs(u, );
for(int i = ; i <= n; i++) if(layer[i] > ) ans++;
printf("%d\n", ans - );
}
return ;
}
BFS版本
//1076 Forwards on Weibo
#include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
vector <int> E[N];
bool vis[N];
int n, m, k, u, sz; void bfs() {
int ans = ;
for(int i = ; i <= n; i++) vis[i] = ;
queue < pair<int,int> > Q;
Q.push(make_pair(u, ));
vis[u] = ;
while(!Q.empty()) {
int cur = Q.front().first;
int layer = Q.front().second;
Q.pop();
if(layer >= k) continue;
for(int i = ; i < E[cur].size(); i++) {
int v = E[cur][i];
if(!vis[v]) {
ans++;
vis[v] = ;
Q.push(make_pair(v, layer + ));
}
}
}
printf("%d\n", ans);
} int main() {
scanf("%d %d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &sz);
while(sz) {
sz--;
scanf("%d", &u);
E[u].push_back(i);
}
}
scanf("%d", &m);
while(m--) {
scanf("%d", &u);
bfs();
}
return ;
}
1077 Kuchiguse
模拟
//1077 Kuchiguse
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; int id[];
char s[][]; int main() {
int n, cnt = ;
scanf("%d", &n);
getchar();
for(int i = ; i <= n; i++) {
char c;
while(scanf("%c", &c) != EOF && c != '\n') {
s[i][id[i]++] = c;
}
}
while() {
for(int i = ; i <= n; i++) {
if( ((id[i] - cnt) < ) || (s[i][id[i] - cnt] != s[][id[] - cnt]) ) {
cnt--;
if(cnt == ) printf("nai");
else {
for(int i = id[] - cnt; i < id[] ; i++) {
printf("%c", s[][i]);
}
}
return ;
}
}
cnt++;
}
return ;
}
1078 Hashing
Hash二次探测。0^2，1^2，2^2...。
//1078 Hashing
#include <iostream>
using namespace std; const int N = 1e4 + ;
bool vis[N]; bool check(int x) {
if(x < ) return false;
for(int i = ; i * i <= x; i++) {
if(x % i == ) return false;
}
return true;
} int main() {
int n, m, p;
cin >> m >> n;
while(!check(m)) {m++;}
for(int i = ; i <= n; i++) {
bool f = ;
cin >> p;
if(i != ) printf(" ");
for(int i = ; i < m; i++) {
int tmp = (p + i * i) % m;
if(!vis[tmp]) {
f = ;
printf("%d", tmp);
vis[tmp] = ;
break;
}
}
if(!f) printf("-");
}
return ;
}
1079 Total Sales of Supply Chain
从根跑一遍DFS到叶子节点。统计每个叶子节点的能够产生的销售额。
//1079 Total Sales of Supply Chain
#include <vector>
#include <cstdio>
using namespace std; const int N = 1e5 + ;
int cnt[N];
bool vis[N];
double p, r;
double price[N];
vector <int> E[N]; void dfs(int u, double val) {
vis[u] = ; price[u] = val;
for(int i = ; i < E[u].size(); i++) {
int v = E[u][i];
if(!vis[v]) dfs(v, val * ( + r / ));
}
} int main() {
int n, k, u;
scanf("%d %lf %lf", &n, &p, &r);
for(int i = ; i < n; i++) {
scanf("%d", &k);
if(k == ){
scanf("%d", &cnt[i]);
} else {
while(k--) {
scanf("%d", &u);
E[i].push_back(u);
}
}
}
double ans = ;
dfs(, p);
for(int i = ; i < n; i++) {
ans += price[i] * cnt[i];
}
printf("%.1f\n", ans);
return ;
}
1080 Graduate Admission
按照题意模拟，用set从小到大排序特性会方便很多。
// 1080 Graduate Admission
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 4e4 + ;
struct Stu{
int Id, Ge, Gi, Gh, Rank;
int choices[];
}; struct Sch{
int maxn, lastRank;
set<int> admit;
}; bool cmp(Stu x, Stu y){
if(x.Gh == y.Gh) return x.Ge > y.Ge;
return x.Gh > y.Gh;
} set<int>::iterator it; int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vector<Sch> sch(m);
vector<Stu> stu(n);
for(int i = ; i < m; i++) scanf("%d", &sch[i].maxn);
for(int i = ; i < n; i++){
scanf("%d%d", &stu[i].Ge, &stu[i].Gi);
stu[i].Id=i; stu[i].Gh = stu[i].Ge + stu[i].Gi;
for(int j = ; j < k; j++) scanf("%d", &stu[i].choices[j]);
}
sort(stu.begin(), stu.end(), cmp);
int Rank = ;
for(int i = ; i < n; i++){
if(i== || (stu[i].Gh == stu[i-].Gh && stu[i].Gi == stu[i-].Gi)) stu[i].Rank = Rank;
else{
Rank = i + ;
stu[i].Rank = Rank;
}
}
for(int i = ; i < n; i++){
bool f=;
for(int j = ; j < k; j++){
int schid = stu[i].choices[j];
if(sch[schid].maxn > ){
sch[schid].admit.insert(stu[i].Id);
sch[schid].maxn--;
sch[schid].lastRank = stu[i].Rank;
f = true;
}else if(sch[schid].lastRank == stu[i].Rank) {
sch[schid].admit.insert(stu[i].Id);
f = true;
}
if(f) break;
}
}
for(int i = ; i < m; i++){
for(it = sch[i].admit.begin(); it!=sch[i].admit.end(); it++){
if(it == sch[i].admit.begin()) printf("%d", *it);
else printf(" %d", *it);
}
printf("\n");
}
return ;
}
1081 Rational Sum
通分，注意最后若答案为0的时的格式输出。
// 1081 Rational Sum
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long ll;
ll a[], b[]; int main() {
ll n, nr = , dm = ;
scanf("%lld", &n);
for(ll i = ; i <= n; i++) {
scanf("%lld/%lld", &a[i], &b[i]);
dm = b[i] / __gcd(b[i], dm) * dm;
}
for(ll i = ; i<= n; i++) {
nr = nr + (dm / b[i]) * a[i];
}
ll g = __gcd(nr, dm);
if(g != ) nr /= g, dm /= g;
if(nr / dm) {
printf("%lld", nr / dm);
nr = nr - (nr / dm) * dm;
if(nr != ) printf(" %lld/%lld", nr, dm);
return ;
}
nr = nr - (nr / dm) * dm;
if(nr != ) printf("%lld/%lld", nr, dm);
else printf("");
return ;
}
1082 Read Number in Chinese
模拟，注意细节即可。
// 1082 Read Number in Chinese
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; string a[] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
string b[] = {"","Shi","Bai","Qian","Wan","Shi","Bai","Qian","Yi"}; int main() {
int n, f = ;
string s;
cin >> s;
if(s[] == '-') {
cout << "Fu" << " ";
s = s.substr();
}
n = s.size();
reverse(s.begin(), s.end());
for(int i = n - ; i >= ; i--) {
if(i == n - ) {
cout << a[s[i] - ''] << " " << b[i];
} else {
if(s[i] != '') {
if(f) {
cout << " " << a[];
f = ;
}
cout << " " << a[s[i] - ''] << " " << b[i];
} else {
f = ;
if(i == ) cout << " " << b[];
}
}
}
if(f && s[] != '') {
cout << " " << a[];
}
if(s.size() == ) {
cout << a[s[] - ''];
}
else if(s.size() > && s[] != ''){
cout << " " << a[s[] - ''];
}
return ;
}
1083 List Grades
结构体排序
// 1083 List Grades
#include <cstdio>
#include <algorithm>
using namespace std; const int N = 2e5 + ;
struct node {
char name[], id[];
int grade;
}recoder[N]; bool cmp(node x, node y) {
return x.grade > y.grade;
} int main() {
bool f = ;
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%s %s %d", recoder[i].name, recoder[i].id, &recoder[i].grade);
}
int g1, g2;
scanf("%d%d", &g1, &g2);
sort(recoder + , recoder + + n, cmp);
for(int i = ; i <= n; i++) {
if(recoder[i].grade <= g2 && recoder[i].grade >= g1) {
printf("%s %s\n", recoder[i].name, recoder[i].id);
f = ;
}
}
if(!f) printf("NONE\n");
return ;
}
map标记一下。
// 1084 Broken Keyboard
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; map <char, int> m; int main() {
char c;
string s1, s2;
cin >> s1 >> s2;
for(int i = ; i < s2.size(); i++) {
m[s2[i]] = ;
if(s2[i] >= 'a' && s2[i] <= 'z') {
c = s2[i] - ;
m[c] = ;
}
else if(s2[i] >= 'A' && s2[i] <= 'Z') {
c = s2[i] + ;
m[c] = ;
}
}
for(int i = ; i < s1.size(); i++) {
if(!m[s1[i]]) {
m[s1[i]] = ;
if(s1[i] >= 'a' && s1[i] <= 'z') {
c = s1[i] - ;
m[c] = ;
cout << c;
}
else if(s1[i] >= 'A' && s1[i] <= 'Z') {
c = s1[i] + ;
m[c] = ;
cout << s1[i];
} else {
cout << s1[i];
}
}
}
return ;
}
1085 Perfect Sequence
二分搜索
// 1085 Perfect Sequence
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = 1e5 + ;
ll a[N]; int main() {
int ans = ;
ll n, p;
scanf("%lld %lld", &n, &p);
for(int i = ; i < n; i++) scanf("%lld", &a[i]);
sort(a, a + n);
for(int i = ; i < n; i++) {
int pos1 = lower_bound(a, a + n, a[i]) - a;
int pos2 = lower_bound(a, a + n, a[i] * p + ) - a;
pos2--;
ans = max(ans, pos2 - pos1 + );
}
printf("%d\n", ans);
return ;
}
1086 Tree Traversals Again
由题目可以得知push的时候为往下找，分情况讨论存左孩子还是右孩子，pop的时候表示往右走，下一次push存右孩子，最后后序遍历一下即可。
// 1086 Tree Traversals Again
#include <stack>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; char s[];
struct node{
int lch, rch;
}tree[];
stack <int> sta;
int n, u, fa, root = -, child = ; void postorder(int u) {
if(tree[u].lch != ) postorder(tree[u].lch);
if(tree[u].rch != ) postorder(tree[u].rch);
if(u == root) printf("%d", u);
else printf("%d ", u);
} int main() {
scanf("%d", &n);
n *= ;
while(n--) {
scanf("%s", s);
if(s[] == 'u') {
scanf("%d", &u);
sta.push(u);
if(root == -) {
root = u;
} else {
if(child == ) tree[fa].lch = u;
else tree[fa].rch = u;
}
fa = u;
child = ;
} else {
if(sta.size())
fa = sta.top();
sta.pop();
child = ;
}
}
postorder(root);
return ;
}
1087 All Roads Lead to Rome
先Floyd得到最短路，再DFS搜，搜的过程中更新答案。
// 1087 All Roads Lead to Rome
#include <bits/stdc++.h>
using namespace std; const int N = ;
int n, m, cost, cnt = , maxhappy = ;
int happy[N], d[N][N];
string s[N], s1, s2;
map<string, int> mp;
vector<int> E[N], res, ans;
bool vis[N]; void dfs(int u, int en, int co) {
if(u == en && co == cost) {
int sum = ;
for(int i = ; i < res.size(); i++) {
sum += happy[res[i]];
}
if(sum > maxhappy) {
maxhappy = sum;
ans.clear();
for(int i = ; i < res.size(); i++) ans.push_back(res[i]);
}
else if(sum == maxhappy && res.size() < ans.size()) {
ans.clear();
for(int i = ; i < res.size(); i++) ans.push_back(res[i]);
}
cnt++;
return ;
}
for(int k = ; k < E[u].size(); k++) {
int v = E[u][k];
if(vis[v]) continue;
res.push_back(v);
vis[v] = ;
dfs(v, en, co + d[u][v]);
vis[v] = ;
res.pop_back();
}
} int main() {
cin >> n >> m >> s[];
mp[s[]] = ;
memset(d, 0x3f, sizeof(d));
for(int i = ; i <= n; i++) d[i][i] = ;
for(int i = ; i <= n; i++) {
cin >> s[i] >> happy[i];
mp[s[i]] = i;
}
for(int i = ; i <= m; i++) {
cin >> s1 >> s2 >> cost;
d[mp[s1]][mp[s2]] = cost;
d[mp[s2]][mp[s1]] = cost;
E[mp[s2]].push_back(mp[s1]);
E[mp[s1]].push_back(mp[s2]);
} for(int k = ; k <= n; k++)
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
d[i][j] = min(d[i][j] ,d[i][k] + d[k][j]); cost = d[mp[s[]]][mp["ROM"]];
vis[mp[s[]]] = ;
dfs(mp[s[]], mp["ROM"], ); cout << cnt << " " << cost << " " << maxhappy << " " << maxhappy / ans.size() << endl;
cout << s[];
for(int i = ; i < ans.size(); i++) cout << "->" << s[ans[i]];
return ;
}
1088 Rational Arithmetic
注意相乘会爆long long，判断负可以分别判断x 和 y
// 1088 Rational Arithmetic
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
ll gcd(ll a, ll b) {
return b == ? a : gcd(b, a % b);
} void func(ll x, ll y) {
bool f = ;
if(x * y == ) {
if(y == ) printf("Inf");
else if(x == ) printf("");
return ;
}
if((x > && y < ) || (x < && y > )) f = ;
x = abs(x); y = abs(y);
ll val = x / y;
ll res = x - val * y;
if(f) printf("(-");
if(val != ) printf("%lld", val);
if(res == ) {
if(f) printf(")");
return ;
}
if(val != ) printf(" ");
ll g = gcd(res, y);
res /= g; y /= g;
printf("%lld/%lld", res, y);
if(f) printf(")");
} int main() {
ll a, b, c, d;
scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
func(a, b);printf(" + ");func(c, d);printf(" = ");func(a * d + b * c, b * d);printf("\n");
func(a, b);printf(" - ");func(c, d);printf(" = ");func(a * d - b * c, b * d);printf("\n");
func(a, b);printf(" * ");func(c, d);printf(" = ");func(a * c, b * d);printf("\n");
func(a, b);printf(" / ");func(c, d);printf(" = ");func(a * d, b * c);
return ;
}
1089 Insert or Merge
先判断是否为插入排序，不是的话，跑一遍归并，直到a数组和b数组一样，再进行一次归并操作。
// 1089 Insert or Merge
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int a[N], b[N]; int main() {
int n, i, j;
cin >> n;
for (i = ; i < n; i++) cin >> a[i];
for (i = ; i < n; i++) cin >> b[i];
for (i = ; i < n - && b[i] <= b[i + ]; i++);
for (j = i + ; a[j] == b[j] && j < n; j++);
if (j == n) {
cout << "Insertion Sort" << endl;
sort(a, a + i + );
} else {
cout << "Merge Sort" << endl;
int k = , f = ;
while(f) {
f = ;
for (i = ; i < n; i++) {
if (a[i] != b[i]) f = ;
}
k = k * ;
for (i = ; i < n / k; i++)
sort(a + i * k, a + (i + ) * k);
sort(a + n / k * k, a + n);
}
}
for(j = ; j < n; j++) {
if (j != ) cout << " ";
cout << a[j];
}
return ;
}
1090 Highest Price in Supply Chain
DFS跑一遍树即可。
// 1090 Highest Price in Supply Chain
#include <cstdio>
#include <vector>
using namespace std; const int N = 1e5 + ;
int n, u, cnt, root;
double p, r, maxp = , sellp[N];
vector <int> E[N]; void dfs(int a, double price) {
sellp[a] = price;
maxp = max(maxp, price);
for(int i = ; i < E[a].size(); i++) {
int b = E[a][i];
dfs(b, price * (1.0 + r / ));
}
} int main() {
scanf("%d %lf %lf", &n, &p, &r);
for(int i = ; i < n; i++) {
scanf("%d", &u);
if(u == -) root = i;
else E[u].push_back(i);
}
dfs(root, p);
for(int i = ; i < n; i++) {
if(sellp[i] == maxp) cnt++;
}
printf("%.2f %d\n", maxp, cnt);
return ;
}
1091 Acute Stroke
3维BFS裸题。
// 1091 Acute Stroke
#include <queue>
#include <cstdio>
using namespace std; int n, m, l, t, ans = ;
int mp[][][];
bool vis[][][];
struct node{
int z, x, y;
};
int dx[] = {, , , , -, };
int dy[] = {, , -, , , };
int dz[] = {-, , , , , }; bool check(int z, int x, int y) {
if(z >= && z <= l && x >= && x <= n && y >= && y <= m) return true;
return false;
} int bfs(int z, int x, int y) {
queue <node> q;
node tmp;
int res = ;
q.push(node{z, x, y});
vis[z][x][y] = ;
while(!q.empty()) {
res++;
tmp = q.front();
q.pop();
for(int i = ; i < ; i++) {
int nz = tmp.z + dz[i];
int nx = tmp.x + dx[i];
int ny = tmp.y + dy[i];
if(check(nz, nx, ny) && !vis[nz][nx][ny] && mp[nz][nx][ny]) {
vis[nz][nx][ny] = ;
q.push(node{nz, nx, ny});
}
} }
if(res >= t) return res;
else return ;
} int main() {
scanf("%d%d%d%d", &n, &m, &l, &t);
for(int z = ; z <= l; z++)
for(int x = ; x <= n; x++)
for(int y = ; y <= m; y++)
scanf("%d", &mp[z][x][y]); for(int z = ; z <= l; z++)
for(int x = ; x <= n; x++)
for(int y = ; y <= m; y++)
if(mp[z][x][y] && !vis[z][x][y]) ans += bfs(z, x, y); printf("%d\n", ans);
return ;
}
1092 To Buy or Not to Buy
用数组标记一下即可。
// 1092 To Buy or Not to Buy
#include <iostream>
using namespace std; int a[];
string s1, s2; int main(){
cin >> s1 >> s2;
int c1 = , c2 = ;
for(int i = ; i < s1.size(); i++) a[s1[i]]++;
for(int i = ; i < s2.size(); i++) a[s2[i]]--;
for(int i = ; i < ; i++) {
if(a[i] < ) c1+=a[i];
else c2+=a[i];
}
if(c1 < ) cout << "No " << -c1 << endl;
else cout << "Yes " << c2 << endl;
return ;
}
1093 Count PAT's
统计一下P,A,T。在A位置计算前面有几个P，后面有几个T。
// 1093 Count PAT's
#include <cstdio>
#include <cstring>
using namespace std; typedef long long ll;
const int N = 1e5 + ;
const ll mod = ;
char s[N];
ll sum[N][]; int main() {
int n;
ll ans = ;
scanf("%s", s + );
n = strlen(s + );
for(int i = ; i <= n; i++) {
for(int j = ; j <= ; j++) sum[i][j] = sum[i - ][j];
if(s[i] == 'P') sum[i][]++;
else if(s[i] == 'A') sum[i][]++;
else sum[i][]++;
}
for(int i = ; i <= n; i++) {
if(s[i] == 'A') {
ans = (ans + (sum[i][] * (sum[n][] - sum[i][])) % mod) % mod;
}
}
printf("%lld\n", ans);
return ;
}
1094 The Largest Generation
DFS跑下树，记录下即可。
// 1094 The Largest Generation
#include <vector>
#include <cstdio>
using namespace std; const int N = ;
int n, m, cnt[N];
vector <int> children[N]; void dfs(int u, int level) {
for(int i = ; i < children[u].size(); i++) {
dfs(children[u][i], level + );
}
cnt[level]++;
} int main() {
scanf("%d%d", &n, &m);
while(m--) {
int r, k, c;
scanf("%d%d", &r, &k);
while(k--) {
scanf("%d", &c);
children[r].push_back(c);
}
}
dfs(, );
int mx = , id;
for(int i = ; i <= n; i++) {
if(cnt[i] > mx) {
mx = cnt[i];
id = i;
}
}
printf("%d %d\n", mx, id);
return ;
}
1095 Cars on Campus
按同个车牌号并以时间排序，模拟过去即可。
// 1095 Cars on Campus
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
char s[N][], op[];
int t[N], f[N], id[N];
int cnt[ * + ], maxtime;
map<string, int> m;
vector <string> ans; bool cmp(int x, int y) {
if(!strcmp(s[x], s[y])) {
return t[x] < t[y];
} else {
return strcmp(s[x], s[y]) < ;
}
} int main() {
int n, k, hh, mm, ss;
scanf("%d%d", &n, &k);
for(int i = ; i < n; i++) {
id[i] = i;
scanf("%s %d:%d:%d %s", s[i], &hh, &mm, &ss, op);
t[i] = * hh + * mm + ss;
if(op[] == 'i') f[i] = ;
else f[i] = ;
}
sort(id, id + n, cmp);
for(int i = ; i < n; i++) {
if(!strcmp(s[id[i]], s[id[i - ]])) {
if(f[id[i - ]] == && f[id[i]] == ) {
cnt[t[id[i - ]]]++;
cnt[t[id[i]]]--;
m[s[id[i]]] = m[s[id[i]]] + t[id[i]] - t[id[i - ]];
maxtime = max(maxtime, m[s[id[i]]]);
}
}
}
for(int i = ; i <= * ; i++) cnt[i] += cnt[i - ];
while(k--) {
scanf("%d:%d:%d", &hh, &mm, &ss);
hh = * hh + * mm + ss;
printf("%d\n", cnt[hh]);
}
for(int i = ; i < n; i++) {
if(m[s[i]] == maxtime) {
ans.push_back(s[i]);
m[s[i]] = ;
}
}
sort(ans.begin(), ans.end());
for(int i = ; i < ans.size(); i++) cout << ans[i] << " ";
hh = maxtime / ; maxtime -= * hh;
mm = maxtime / ; maxtime -= * mm;
ss = maxtime;
printf("%02d:%02d:%02d\n", hh, mm, ss);
return ;
}
1096 Consecutive Factors
暴力找起点，然后找可以被整除的数。
// 1096 Consecutive Factors
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll; int main() {
ll n, f = , maxlen = ;
cin >> n;
for(ll i = ; i * i <= n; i++){
ll m = , j = i;
for(; j * j <= n; j++) {
m *= j;
if(n % m != ) break;
}
if(j - i > maxlen) {
maxlen = j - i;
f = i;
}
}
if(f == ) {
cout << << endl << n << endl;
return ;
}
cout << maxlen << endl;
ll tmp = ;
cout << f;
for(ll i = f + ; tmp < n && (i - f) < maxlen; i++) {
tmp *= i;
cout << "*" << i;
}
return ;
}
1097 Deduplication on a Linked List
从根跑下树，把仍然保留的移除的都存起来。最后输出即可。
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int nxt[N], val[N];
map<int, int> m; struct node{
int u, w, v;
}; vector <node> Remain, Remove; int main() {
int root, cur, n;
scanf("%d %d", &root, &n);
for(int i = ; i <= n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &w, &v);
nxt[u] = v;
val[u] = w;
}
cur = root;
while(cur != -) {
if(!m[abs(val[cur])]) {
Remain.push_back({cur, val[cur], nxt[cur]});
m[abs(val[cur])] = ;
} else {
Remove.push_back({cur, val[cur], nxt[cur]});
}
cur = nxt[cur];
}
for(int i = ; i < Remain.size(); i++) {
if(i != Remain.size() - ) printf("%05d %d %05d\n", Remain[i].u, Remain[i].w, Remain[i + ].u);
else printf("%05d %d -1\n", Remain[i].u, Remain[i].w);
}
for(int i = ; i < Remove.size(); i++) {
if(i != Remove.size() - ) printf("%05d %d %05d\n", Remove[i].u, Remove[i].w, Remove[i + ].u);
else printf("%05d %d -1\n", Remove[i].u, Remove[i].w);
}
return ;
}
1098 Insertion or Heap Sort
判断下排序类型，插入排序很容易解决，再扔个堆排序上去即可。
// 1098 Insertion or Heap Sort
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int a[N], b[N]; void solve(int l, int r) {
int i = , j = ;
while(j <= r) {
if(j + <= r && b[j] < b[j + ]) j++;
if(b[j] > b[i]) {
swap(b[j], b[i]);
i = j;
j = * (i + ) -;
} else {
break;
}
}
} int main() {
int n, k, f = ;
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", &a[i]);
for(int i = ; i < n; i++) scanf("%d", &b[i]);
for(k = ; k < n - && b[k] <= b[k + ]; k++) ;
for(int i = k + ; i < n; i++) {
if(a[i] != b[i]) {f = ; break;}
}
if(f) {
printf("Insertion Sort\n");
sort(b, b + k + );
for(int i = ; i < n; i++){
printf("%d", b[i]);
if(i != n - ) printf(" ");
}
} else {
printf("Heap Sort\n");
int p = n - ;
while(p > && b[p - ] <= b[p]) {
p--;
}
swap(b[], b[p]);
solve(, p - );
for(int i = ; i < n; i++){
printf("%d", b[i]);
if(i != n - ) printf(" ");
}
}
return ;
}
1099 Build A Binary Search Tree
先排序，中序遍历即为填数的顺序。最后再层次遍历输出。
// 1099 Build A Binary Search Tree
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; queue <int> q;
const int N = ;
int lch[N], rch[N], val[N], a[N], cnt = ; void dfs(int u) {
if(lch[u] != -) dfs(lch[u]);
val[u] = a[cnt++];
if(rch[u] != -) dfs(rch[u]);
} int main() {
int n, f = ;
scanf("%d", &n);
for(int i = ; i < n; i++) {
int l, r;
scanf("%d %d", &l, &r);
lch[i] = l; rch[i] = r;
}
for(int i = ; i < n; i++) scanf("%d", &a[i]);
sort(a, a + n);
dfs();
q.push();
while(!q.empty()) {
int cur = q.front();
q.pop();
if(!f) f = ;
else printf(" ");
printf("%d", val[cur]);
if(lch[cur] != -) q.push(lch[cur]);
if(rch[cur] != -) q.push(rch[cur]);
}
return ;
}
1100 Mars Numbers
模拟。
// 1100 Mars Numbers
#include <iostream>
using namespace std; string s;
string str[] = {
"tret", "jan", "feb", "mar", "apr", "may", "jun",
"jly", "aug", "sep", "oct", "nov", "dec", "tam", "hel",
"maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok",
"mer", "jou"
}; void cal1() {
if(s[] == '') {
cout << "tret" << endl;
return ;
}
int num = ;
for(int i = ; i < s.size(); i++) num = * num + (s[i] - '');
if(num / ) cout << str[num / + ];
if((num / ) && (num % )) cout << " ";
if(num % ) cout << str[num % ];
cout << endl;
} void cal2() {
int t1 = , t2 = ;
string s1 = s.substr(, ), s2 = "";
if(s.size() > ) s2 = s.substr(, );
for(int i = ; i <= ; i++) {
if(str[i] == s1) t1 = i;
if(str[i] == s2) t2 = i;
}
if(t1 > ) cout << (t1 - ) * + t2 << endl;
else cout << t1 + t2 << endl;
} int main() {
int n;
cin >> n;
getchar();
for(int i = ; i <= n; i++) {
getline(cin, s);
if(s[] >= '' && s[] <= '') cal1();
else cal2();
}
return ;
}
1101 Quick Sort
用个数组记录下从前往后，对于当前位置的最大值；从后往前，对于当前位置的最小值。最后再遍历一遍数组即可。
// 1101 Quick Sort
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; vector <int> ans;
const int N = 1e5 + ;
int a[N], pre[N], nxt[N]; int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i <= n; i++) {
pre[i] = max(pre[i - ], a[i]);
}
nxt[n + ] = 1e9 + ;
for(int i = n; i >= ; i--) {
nxt[i] = min(nxt[i + ], a[i]);
}
for(int i = ; i <= n; i++) {
if(pre[i] <= a[i] && nxt[i] >= a[i]) {
ans.push_back(a[i]);
}
}
printf("%d\n", ans.size());
sort(ans.begin(), ans.end());
for(int i = ; i < ans.size(); i++) {
if(i == ) printf("%d", ans[i]);
else printf(" %d", ans[i]);
}
printf("\n");
return ;
}
1102 Invert a Binary Tree
先找下根，中序和层序，把先左后右的顺序调换下。
// 1102 Invert a Binary Tree
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int n, root, f;
int lch[N], rch[N], fa[N]; void level_order() {
queue <int> q;
q.push(root);
while(!q.empty()) {
int u = q.front();
if(!f) f = ;
else printf(" ");
printf("%d", u);
q.pop();
if(rch[u] != -) q.push(rch[u]);
if(lch[u] != -) q.push(lch[u]);
}
printf("\n");
} void in_order(int u) {
if(rch[u] != -) in_order(rch[u]);
if(!f) f = ;
else printf(" ");
printf("%d", u);
if(lch[u] != -) in_order(lch[u]);
} int main() {
cin >> n;
memset(fa, -, sizeof(fa));
memset(lch, -, sizeof(lch));
memset(rch, -, sizeof(rch));
for(int i = ; i < n; i++) {
char c1, c2;
cin >> c1 >> c2;
if(c1 != '-') {
lch[i] = (c1 - '');
fa[(c1 - '')] = i;
}
if(c2 != '-') {
rch[i] = (c2 - '');
fa[(c2 - '')] = i;
}
}
for(int i = ; i < n; i++){
if(fa[i] == -) root = i;
}
f = ;
level_order();
f = ;
in_order(root);
printf("\n");
return ;
}
1103 Integer Factorization
预处理下，再DFS+剪枝。更新下答案。
// 1103 Integer Factorization
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; int a[], b[], ans[];
int n, m, k, c; void dfs(int id, int cnt, int val) {
b[cnt] = id;
if(cnt > m || val > n) return ;
if(val == n && cnt == m) {
bool f = ;
for(int i = ; i <= m; i++) {
if(ans[i] != b[i]) {
if(b[i] > ans[i]) f = ;
break;
}
}
for(int i = ; i <= m; i++) ans[i] = b[i];
return ;
}
for(int i = id; i <= c && val + a[i] <= n; i++) {
dfs(i, cnt + , val + a[i]);
}
} int POW(int u, int v) {
int res = ;
for(int i = ; i <= v; i++) res *= u;
return res;
} int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i = ; POW(i, k) <= n; i++) {
a[i] = POW(i, k);
c = i;
}
for(int i = ; i <= c; i++) dfs(i, , a[i]);
int res = ;
for(int i = ; i <= m; i++) res += a[ans[i]];
if(res == n) {
printf("%d = %d^%d", n, ans[m], k);
for(int i = m - ; i >= ; i--) {
printf(" + %d^%d", ans[i], k);
}
printf("\n");
} else {
printf("Impossible\n");
}
return ;
}
1104 Sum of Number Segments
每个位置会算到的次数为$i * (n - i + 1)$。
#include <cstdio>
using namespace std; const int N = 1e5 + ;
double a[N]; int main() {
int n;
double ans = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%lf", &a[i]);
for(int i = ; i <= n; i++) {
ans += a[i] * i * (n - i + );
}
printf("%.2f\n", ans);
return ;
}
1105 Spiral Matrix
蛇形填数，注意下细节。
// 1105 Spiral Matrix
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
int a[N];
int ans[N][N]; int main() {
int n, k;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
if(n == ) {
printf("%d", a[]);
return ;
}
sort(a + , a + + n);
int m = sqrt(1.0 * n);
while(n % m != ) m++;
if((n / m) > m) m = n/ m;
//m n/m
k = n; n = n / m;
int i = , j = ;
int U = , D = m, L = , R = n;
while(k > ) {
while(k > && j < R) {
ans[i][j] = a[k--];
j++;
}
while(k > && i < D) {
ans[i][j] = a[k--];
i++;
}
while(k > && j > U) {
ans[i][j] = a[k--];
j--;
}
while(k > && i > L) {
ans[i][j] = a[k--];
i--;
}
U++; D--; L++; R--;
i++; j++;
if(k == ) {
ans[i][j] = a[k--];
}
}
for(int i = ; i <= m; i++) {
for(int j = ; j <= n; j++) {
printf("%d%c", ans[i][j], (j == n) ? '\n' : ' ');
}
}
return ;
}
1106 Lowest Price in Supply Chain
跑下树。在叶子节点更新下最小值，最后再遍历下叶子节点即可。
// 1106 Lowest Price in Supply Chain
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
int n, k, id;
double p, r, val[N], mi = 1e12;
vector <int> E[N]; void dfs(int u) {
if(E[u].size() == ) mi = min(mi, val[u]);
for(int j = ; j < E[u].size(); j++) {
int v = E[u][j];
val[v] = val[u] * (1.0 + r / 100.0);
dfs(v);
}
} int main() {
scanf("%d %lf %lf", &n, &p, &r);
for(int i = ; i < n; i++) {
scanf("%d", &k);
for(int j = ; j <= k; j++) {
scanf("%d", &id);
E[i].push_back(id);
}
}
val[] = p;
dfs();
int cnt = ;
for(int i = ; i < n; i++) if(val[i] == mi && E[i].size() == ) cnt++;
printf("%.4f %d\n", mi, cnt);
return ;
}
1107 Social Clusters
并查集搞搞。
// 1107 Social Clusters
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e3 + ;
vector <int> E[N], ans;
int fa[N], C[N]; int fi(int x) {
return x == fa[x] ? x : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
int fx = fi(x), fy = fi(y);
if(fx != fy) {
fa[fy] = fx;
}
} int main() {
bool f = ;
int n, k, u, cnt = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
fa[i] = i;
scanf("%d:", &k);
while(k--) {
scanf("%d", &u);
E[u].push_back(i);
}
}
for(int i = ; i < N; i++) {
for(int j = ; j < E[i].size(); j++) {
u = E[i][j];
Union(u, E[i][]);
}
}
for(int i = ; i <= n; i++) {
C[fi(i)]++;
if(i == fa[i]) cnt++;
}
printf("%d\n", cnt);
for(int i = ; i <= n; i++) {
if(C[i] != ) ans.push_back(C[i]);
}
sort(ans.begin(), ans.end());
for(int i = ans.size() - ; i >= ; i--) {
if(i != ans.size() - ) printf(" ");
printf("%d", ans[i]);
}
return ;
}
1108 Finding Average
注意 一个合法数字 的输出格式。
// 1108 Finding Average
#include <cstdio>
#include <cstring>
using namespace std; char str[]; double check() {
int i = , f = , cnt = ;
if(str[] == '-') i = , f = -;
int m = strlen(str);
for(; i < m; i++) {
if(str[i] >= '' && str[i] <= '') continue;
if(str[i] == '.') {
cnt++;
if(cnt >= ) return ;
}
else return ;
}
double res = ;
i = ;
if(str[] == '-') i = , f = -;
for(; i < m; i++) {
if(str[i] == '.') {
if(i + < m) return ;
if(i + < m) res += (str[i + ] - '') / 100.0;
if(i + < m) res += (str[i + ] - '') / 10.0;
return f * res;
}
res = * res + 1.0 * (str[i] - '');
}
return f * res;
} int main() {
double average = ;
int n, c = ;
scanf("%d", &n);
while(n--) {
scanf("%s", str);
double val = check();
if(val >= - && val <= ) average += check(), c++;
else{
printf("ERROR: %s is not a legal number\n", str);
}
}
if(c == ) printf("The average of %d number is %.2f\n", c, average / c);
else if(c > ) printf("The average of %d numbers is %.2f\n", c, average / c);
else printf("The average of 0 numbers is Undefined\n");
return ;
}
1109 Group Photo
模拟。
// 1109 Group Photo
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; struct node {
int h;
string name;
} tmp; bool cmp(node x, node y) {
if(x.h == y.h) return x.name < y.name;
return x.h > y.h;
} vector<node> p; int main() {
int n, k, per, last, id = ;
cin >> n >> k;
per = n / k;
last = per + (n % k);
for (int i = ; i <= n; i++) {
cin >> tmp.name >> tmp.h;
p.push_back(tmp);
}
sort(p.begin(), p.end(), cmp);
for (int i = ; i < k; i++) {
int now = per, f = -;
if(i == ) now = last;
int pos = now / ;
vector<string> ans(n);
while(pos >= && pos < now) {
ans[pos] = p[id++].name;
pos += f;
if(f < ) {
f *= -;
f++;
} else {
f *= -;
f--;
}
}
for (int j = ; j < now; j++) {
cout << ans[j];
if(j != now - ) cout << " ";
else cout << endl;
}
ans.clear();
}
return ;
}
1110 Complete Binary Tree
完全二叉树递归出的最大下标值一定等于总节点数。
// 1110 Complete Binary Tree
#include <queue>
#include <iostream>
using namespace std; int fa[], lch[], rch[];
int n, root, last, maxindex = ; void dfs(int u, int index) {
if(u == -) return ;
if(index > maxindex) {
maxindex = index;
last = u;
}
dfs(lch[u], * index);
dfs(rch[u], * index + );
} int main() {
cin >> n;
for(int i = ; i < n; i++) fa[i] = lch[i] = rch[i] = -;
for(int i = ; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
if(s1 != "-") {
fa[atoi(s1.c_str())] = i;
lch[i] = atoi(s1.c_str());
}
if(s2 != "-") {
fa[atoi(s2.c_str())] = i;
rch[i] = atoi(s2.c_str());
}
}
for(int i = ; i < n; i++) {
if(fa[i] == -) root = i;
}
dfs(root, );
if(maxindex == n) {
cout << "YES " << last << endl;
} else {
cout << "NO " << root << endl;
}
return ;
}
1112 Stucked Keyboard
模拟。
// 1112 Stucked Keyboard
#include <map>
#include <iostream>
using namespace std; string str;
map<char, int> ok; int main() {
int n, k, c = ;
cin >> k >> str;
n = str.size();
for (int i = ; i < n; i++) {
if(str[i] == str[i - ]) {
c++;
} else {
if(c % k != ) ok[str[i - ]] = ;
c = ;
}
}
if(c > && c % k != ) ok[str[n - ]] = ;
for (int i = ; i < n; i++) {
if(ok[str[i]] == ) {
cout << str[i];
ok[str[i]] = -;
}
}
cout << endl;
c = ;
for (int i = ; i < n; i++) {
if(str[i] == str[i - ]) {
c++;
} else {
if(c % k == ) {
if(ok[str[i - ]] != ) for (int j = ; j <= c / k; j++) cout << str[i - ];
else for (int j = ; j <= c; j++) cout << str[i - ];
}
else {
for (int j = ; j <= c; j++) cout << str[i - ];
}
c = ;
}
}
if(c > && c % k == ) {
if(ok[str[n - ]] != ) for (int j = ; j <= c / k; j++) cout << str[n - ];
else for (int j = ; j <= c; j++) cout << str[n - ];
}
else {
for (int j = ; j <= c; j++) cout << str[n - ];
}
return ;
}
1113 Integer Set Partition
先排序，再前面加一加，后面加一加。
// 1113 Integer Set Partition
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int N = 1e5 + ;
ll a[N]; int main() {
int n, m;
ll s1 = , s2 = ;
cin >> n;
for (int i = ; i <= n; i++) cin >> a[i];
sort(a + , a + + n);
for (int i = n / + ; i <= n; i++) s1 += a[i];
for (int i = ; i < n / + ; i++) s2 += a[i];
cout << (n % ) << " ";
cout << abs(s1 - s2) << endl;
return ;
}
1114 Family Property
暴力模拟即可。
// 1114 Family Property
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; const int N = + ;
int fa[N], M[N], A[N];
int fi(int x) {
return fa[x] == x ? x : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
if(x == - || y == -) return ;
int fx = fi(x), fy = fi(y);
if(fx != fy) {
fa[fx] = fy;
}
} void init() {
for(int i = ; i < N; i++) fa[i] = i;
} int cnt = ;
vector<int> V, E[N];
map<int, int> mp; struct node {
int ansID, ansM;
double avg1, avg2;
}ans[N]; map<int, int> vis; bool cmp(node x, node y) {
if(x.avg2 == y.avg2) return x.ansID < y.ansID;
return x.avg2 > y.avg2;
} int main() {
init();
int n;
cin >> n;
for (int i = ; i <= n; i++) {
int id, father, mother, child, k;
cin >> id >> father >> mother >> k;
Union(id, father);
if(father != -) V.push_back(father);
Union(id, mother);
if(mother != -) V.push_back(mother);
while (k--) {
cin >> child;
if(child != -) V.push_back(child);
Union(id, child);
}
V.push_back(id);
cin >> M[id] >> A[id];
}
for (int i = ; i < V.size(); i++) {
int u = V[i];
if(fa[u] == u && !mp[u]) {
cnt++;
mp[u] = cnt;
}
}
for (int i = ; i < V.size(); i++) {
int u = V[i];
if(!vis[u]) E[mp[fi(u)]].push_back(u), vis[u] = ;
}
for (int i = ; i <= cnt; i++) {
int minid = ;
double sum1 = ;
double sum2 = ;
for(int j = ; j < E[i].size(); j++) {
int v = E[i][j];
minid = min(minid, v);
sum1 += M[v];
sum2 += A[v];
}
ans[i].ansID = minid;
ans[i].ansM = E[i].size();
ans[i].avg1 = sum1 / E[i].size();
ans[i].avg2 = sum2 / E[i].size();
}
sort(ans + , ans + + n, cmp);
cout << cnt << endl;
for (int i = ; i <= cnt; i++) {
printf("%04d %d %.3f %.3f\n", ans[i].ansID, ans[i].ansM, ans[i].avg1, ans[i].avg2);
}
return ;
}
1115 Counting Nodes in a BST
用链表实现二叉搜索树的插入。构建完树后，DFS一遍，在对应深度更新节点数。
// 1115 Counting Nodes in a BST
#include <iostream>
using namespace std; struct node {
int val;
struct node *left, *right;
}; const int N = + ;
int num[N], maxd = -; node *build(node *root, int v) {
if(root == NULL) {
root = new node();
root -> val = v;
root -> left = root -> right = NULL;
} else if(v > root->val) {
root->right = build(root->right, v);
} else {
root->left = build(root->left, v);
}
return root;
} void dfs(node *root, int dp) {
if(root == NULL) {
maxd = max(maxd, dp);
return ;
}
num[dp]++;
dfs(root->left, dp + );
dfs(root->right, dp + );
} int main() {
int n, k;
node *root = NULL;
cin >> n;
while(n--) {
cin >> k;
root = build(root, k);
}
dfs(root, );
cout << num[maxd - ] << " + " << num[maxd - ] << " = " << num[maxd - ] + num[maxd - ] << endl;
return ;
}
1116 Come on! Let's C
模拟。
// 1116 Come on! Let's C
#include <map>
#include <iostream>
using namespace std; map<int, int> Rank; bool check(int x) {
if(x < ) return false;
for(int i = ; i * i <= x; i++) {
if(x % i == ) return false;
}
return true;
} int main() {
int n, k;
cin >> n;
for (int i = ; i <= n; i++) {
cin >> k;
Rank[k] = i;
}
cin >> n;
while (n--) {
cin >> k;
printf("%04d: ", k);
if(Rank[k] == -) cout << "Checked" << endl;
else if(Rank[k] == ) cout << "Are you kidding?" << endl;
else if(Rank[k] == ) cout << "Mystery Award" << endl, Rank[k] = -;
else if(check(Rank[k])) cout << "Minion" << endl, Rank[k] = -;
else cout << "Chocolate" << endl, Rank[k] = -;
}
return ;
}
1117 Eddington Number
前缀和
// 1117 Eddington Number
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e6 + ;
int d[N]; int main() {
int n, k, ans = ;
cin >> n;
for(int i = ; i <= n; i++) {
cin >> k;
d[k]++;
}
for(int i = ; i < N; i++) d[i] += d[i - ];
for(int i = ; i < N; i++) {
if((n - d[i]) >= i) ans = max(ans, i);
}
cout << ans << endl;
return ;
}
1118 Birds in Forest
并查集
// 1118 Birds in Forest
#include <cstdio>
#include <vector>
using namespace std; const int N = 1e4 + ;
bool vis[N];
int fa[N], cnt = ;
vector <int> birds; int fi(int x) {
return x == fa[x] ? x : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
int fx = fi(x), fy = fi(y);
if(fx != fy) {
fa[fx] = fy;
}
} void init() {
for (int i = ; i < N; i++) fa[i] = i;
} int main() {
init();
int m, n, k, u, v;
scanf("%d", &n);
while (n--) {
scanf("%d", &k);
for (int i = ; i <= k; i++) {
scanf("%d", &v);
if(!vis[v]) vis[v] = , birds.push_back(v);
if(i == ) u = v;
else Union(u, v);
}
}
for (int i = ; i < birds.size(); i++) {
u = birds[i];
if(fa[u] == u) cnt++;
}
printf("%d %d\n", cnt, birds.size());
scanf("%d", &m);
while (m--) {
scanf("%d %d", &u, &v);
if(fi(u) == fi(v)) printf("Yes\n");
else printf("No\n");
}
return ;
}
1119 Pre- and Post-order Traversals
通过前序和后序先建棵树。（题目中说明可以随意建棵符合的树）再中序遍历即可。
#include <bits/stdc++.h>
using namespace std; const int maxn=;
int preOrder[maxn], postOrder[maxn];
bool isUnique=true; struct Node{
int left=-,right=-;
}node[maxn]; void build(int preL,int preR,int postL,int postR){
if(preL>=preR){
return;
}
int fa=preL;
int val=preOrder[preL+];
int postIdx;
for(int i=postL;i<postR;i++){
if(val==postOrder[i]){
postIdx=i;
break;
}
}
int num=postIdx-postL;
if(preR-preL-==num){
isUnique=false;
}
node[fa].left=preL+;
build(preL+,preL+num+,postL,postIdx);
if(preR-preL->num){
node[fa].right=preL+num+;
build(preL+num+,preR,postIdx+,postR-);
}
} bool first=true; void inOrder(int root){
if(root==-){
return;
}
inOrder(node[root].left);
if(first){
first=false;
printf("%d",preOrder[root]);
}
else
printf(" %d",preOrder[root]);
inOrder(node[root].right);
} int main(){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&preOrder[i]);
for(int i=;i<=n;i++) scanf("%d",&postOrder[i]);
build(,n,,n);
if(isUnique) printf("Yes\n");
else printf("No\n");
inOrder();
printf("\n");
return ;
}
1120 Friend Numbers
模拟
// 1120 Friend Numbers
#include <set>
#include <cstdio>
#include <iostream>
using namespace std; const int N = 1e4 + ;
int a[N], b[N]; int cal(int x) {
int sum1 = ;
while (x) {
sum1 += x % ;
x /= ;
}
return sum1;
} int check(int x, int y) {
if (x == y) return x;
return ;
} set<int> ans; int main() {
int n;
bool f = ;
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]), b[i] = cal(a[i]);
for (int i = ; i <= n; i++) {
for (int j = i; j <= n; j++) {
int val = check(b[i], b[j]);
if (val) ans.insert(val);
}
}
printf("%d\n", ans.size());
for (auto x : ans) {
if (!f) f = ;
else printf(" ");
printf("%d", x);
}
return ;
}
1121 Damn Single
模拟
// 1121 Damn Single
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; map<int, int> m, vis;
vector<int> p;
const int N = 1e4 + ;
int a[N]; int main() {
int n, x, y;
scanf("%d", &n);
while (n--) {
scanf("%d %d", &x, &y);
x++; y++;
m[x] = y;
m[y] = x;
}
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
a[i]++;
vis[a[i]] = ;
}
for (int i = ; i <= n; i++) {
if (vis[ m[a[i]] ]) continue;
p.push_back(a[i]);
}
sort(p.begin(), p.end());
printf("%d\n", p.size());
for (int i = ; i < p.size(); i++) {
if (i != ) printf(" ");
printf("%05d", p[i] - );
}
return ;
}
1122 Hamiltonian Cycle
模拟
// 1122 Hamiltonian Cycle
#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int MAP[N][N];
set<int> s; int main() {
memset(MAP, -, sizeof(MAP));
int n, m, k;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
MAP[u][v] = ; MAP[v][u] = ;
}
scanf("%d", &k);
while (k--) {
bool f = ;
int u, v, root;
scanf("%d", &m);
scanf("%d", &root);
s.insert(root);
u = root;
for (int i = ; i < m; i++) {
scanf("%d", &v);
s.insert(v);
if (MAP[u][v] == -) f = ;
u = v;
}
if (root != u || s.size() != n || m != n + ) f = ;
if (!f) printf("NO\n");
else printf("YES\n");
s.clear();
}
return ;
}