目录
- 201903
- 201903-2 二十四点
- 201903-3 损坏的RAID5
- 201903-4 消息传递接口
- 201812
- 201812-3 CIDR合并
- 201812-4 数据中心
- 201809
- 201809-3 元素选择器
201903
201903-2 二十四点
可枚举。
写栈的主要思想是:一个数栈\(numSta\),一个运算符栈\(opSta\)。遇到一个运算符,就把之前优先级\(equal\ or\ greater\ than\)它的运算符处理掉。
#include <bits/stdc++.h>
using namespace std;
int operation(int num1, char op, int num2)
{
if (op == '+')
return num1 + num2;
else if (op == '-')
return num1 - num2;
else if (op == 'x')
return num1 * num2;
else
return num1 / num2;
}
int getAns(char s[]) {
stack<int> numSta;
stack<char> opSta;
for (int i = 1; i <= 7; i++)
{
if (s[i] >= '1' && s[i] <= '9')
numSta.push(s[i] - '0');
else
{
if (s[i] == '+' || s[i] == '-')
{
while (!opSta.empty())
{
char op = opSta.top(); opSta.pop();
int num2 = numSta.top(); numSta.pop();
int num1 = numSta.top(); numSta.pop();
numSta.push(operation(num1, op, num2));
}
opSta.push(s[i]);
}
else
{
while (!opSta.empty() && (opSta.top() == 'x' || opSta.top() == '/'))
{
char op = opSta.top(); opSta.pop();
int num2 = numSta.top(); numSta.pop();
int num1 = numSta.top(); numSta.pop();
numSta.push(operation(num1, op, num2));
}
opSta.push(s[i]);
}
}
}
while (!opSta.empty())
{
char op = opSta.top(); opSta.pop();
int num2 = numSta.top(); numSta.pop();
int num1 = numSta.top(); numSta.pop();
numSta.push(operation(num1, op, num2));
}
return numSta.top();
}
int main ()
{
int n;
scanf("%d", &n);
while (n--)
{
char s[10];
scanf("%s", s + 1);
if (getAns(s) == 24)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
201903-3 损坏的RAID5
先吐槽先吐槽!因为输入太大,需要用fgets,读n个字符或读到回车终止。
因为scanf模拟考试T了10+次。因为IO超时的题目都是乐色!(x
用数组存磁盘信息。\(char [1000][40960*2]\)不会爆。静态数据区一般2G大小。
然后就是模拟。计算每个询问块号的条带号、单个磁盘条带号、磁盘号。分情况讨论。
%x小写16进制,%X大写。%d十,%o八,%b二。
#include <bits/stdc++.h>
const int maxn = 1000;
const int maxm = 40960;
using namespace std;
char disk[maxn+10][maxm*2+10];
int vis[maxn+10];
int len, got = 0;
int main()
{
int n, s, l;
scanf("%d%d%d", &n, &s, &l);
memset(vis, 0, sizeof(vis));
for (int i = 1, x; i <= l; i++)
{
scanf("%d ", &x);
vis[x] = 1;
fgets(disk[x], maxm*2 + 10, stdin);
if (!got)
{
len = strlen(disk[x]) / 8 / s - 1;
got = 1;
}
}
int m;
scanf("%d", &m);
while (m--)
{
int b;
scanf("%d", &b);
int stripe = b / s;
int k = stripe / (n-1);
int diskNum = (n - k%n + stripe % (n-1)) % n;
if (k > len || (n-l >= 2 && !vis[diskNum]))
{
printf("-\n");
}
else
{
int st = (k*s + b%s) * 8, en = st + 7;
if (vis[diskNum])
{
for (int i = st; i <= en; i++)
printf("%c", disk[diskNum][i]);
printf("\n");
}
else
{
for (int i = st; i <= en; i++)
{
int ans = 0;
for (int j = 0, tmp; j <= n-1; j++)
{
if (j != diskNum)
{
if (disk[j][i] >= '0' && disk[j][i] <= '9')
{
tmp = disk[j][i] - '0';
}
else
{
tmp = disk[j][i] - 'A' + 10;
}
ans ^= tmp;
}
}
printf("%X", ans);
}
printf("\n");
}
}
}
return 0;
}
201903-4 消息传递接口
求并行的各个进程,且进程内部顺序执行的情况下,会不会出现“死锁”。
首先用\(%[^\n]\)将每个进程读入。最后过不了居然是因为\(str[\ ]\)开小了(悲喜交加。存储在\(<op,\ pid>[\ ]\)中,并记录每个进程的指令数\(instNum[\ ]\)。
然后就是模拟。\(instCmp[\ ]\)记录每个进程已完成的指令数,\(instBlk[\ ]\)记录每个进程是否阻塞,\(numCmp,\ numBlk\)分别是完成和阻塞的进程数。主要思想是:每次执行到某条指令阻塞,然后执行下条指令并循环。判断是否阻塞,就是看\(<op, pid>\)对应的\(pid\)进程当前已完成的指令是否有下一条指令,以及下一条指令是否与之配对。
#include <bits/stdc++.h>
const int maxn = 10000;
using namespace std;
struct tInst
{
int op;
int pid;
};
tInst inst[maxn+10][10];
int instNum[maxn+10];
int instCmp[maxn+10];
int instBlk[maxn+10];
int numCmp, numBlk;
int main ()
{
int T, n;
scanf("%d%d", &T, &n);
getchar();
while (T--)
{
memset(instNum, 0, sizeof(instNum));
for (int i = 0; i <= n - 1; i++)
{
char str[100];
scanf("%[^\n]", str + 1);
getchar();
for (int j = 1, op = 0, pid = 0; ; j++)
{
if (str[j] == 'R')
op = 0;
else if (str[j] == 'S')
op = 1;
else if (str[j] >= '0' && str[j] <= '9')
pid = pid * 10 + str[j] - '0';
else if (str[j] == ' ')
{
inst[i][++instNum[i]].op = op;
inst[i][instNum[i]].pid = pid;
pid = 0;
}
else
{
inst[i][++instNum[i]].op = op;
inst[i][instNum[i]].pid = pid;
break;
}
}
}
memset(instCmp, 0, sizeof(instCmp));
memset(instBlk, 0, sizeof(instBlk));
numCmp = numBlk = 0;
int x = 0;
while (numCmp + numBlk != n)
{
while (instCmp[x] != instNum[x] && !instBlk[x])
{
int y = instCmp[x] + 1;
int op = inst[x][y].op, pid = inst[x][y].pid;
int xx = pid;
if (instCmp[xx] != instNum[xx])
{
int yy = instCmp[xx] + 1;
if (op + inst[xx][yy].op == 1 && x == inst[xx][yy].pid)
{
instCmp[x] ++; instCmp[xx] ++;
if (instCmp[x] == instNum[x])
numCmp ++;
if (instCmp[xx] == instNum[xx])
numCmp ++;
if (instBlk[xx])
{
instBlk[xx] = 0;
numBlk --;
}
}
else
{
instBlk[x] = 1;
numBlk ++;
}
}
else
{
instBlk[x] = 1;
numBlk ++;
}
}
x = (x + 1) % n;
}
if (numCmp == n)
printf("0\n");
else
printf("1\n");
}
return 0;
}
201812
201812-3 CIDR合并
题目想求与给定前缀列表等价的包含IP前缀数目最少的前缀列表。
首先是怎么存储前缀列表。用一个long long存储IP地址,再存一个前缀长度,封装在一个结构体里\(<ipNum, len>\),方便后面排序等操作。IP前缀有三种输入格式,稍微分情况讨论一下。
接着以\(ipNum\)为第一关键字,\(len\)为第二关键字升序排序。
然后考虑去除匹配集被其它IP前缀包含的IP前缀。考虑之前匹配集范围的上届\(mmax\),顺序遍历一下就好了。将剩余的IP列表按之前顺序存在一个静态链表中。
最后将相邻的可合并的IP前缀合并,其实就是前缀长度最后一位0和1,之前完全相同即可。
温习一下链表的插入删除操作。
#include <bits/stdc++.h>
typedef long long LL;
const int maxn = 1000000;
using namespace std;
struct tIP
{
LL ipNum;
int len;
int before, next;
tIP()
{
before = next = -1;
}
bool operator < (const tIP &y) const
{
if(ipNum == y.ipNum)
return len < y.len;
return ipNum < y.ipNum;
}
void show()
{
LL num[5];
LL temp = ipNum;
for (int i = 4; i >= 1; i--)
{
num[i] = temp % 256;
temp /= 256;
}
for (int i = 1; i <=4; i++)
{
printf("%lld", num[i]);
if (i == 4)
printf("/");
else
printf(".");
}
printf("%d\n", len);
}
};
tIP ip[maxn+10];
LL getMMax(tIP iip)
{
LL temp = (1LL << (32-iip.len)) - 1;
return iip.ipNum | temp;
}
int main()
{
int n;
scanf("%d", &n);
char s[30];
for (int id = 1, slash, dotCnt, style; id <= n; id++)
{
slash = 0;
dotCnt = 0;
scanf("%s", s + 1);
for (int i = 1; s[i] != '\0'; i++)
{
if (s[i] == '/')
slash = 1;
if (s[i] == '.')
dotCnt ++;
}
if (slash == 1 && dotCnt == 3)
style = 1;
else if (slash == 1 && dotCnt < 3)
style = 2;
else
style = 3;
LL num[5];
memset(num, 0, sizeof(num));
if (style == 1 || style == 2)
{
for (int i = 1, temp = 0, numCnt = 1; ; i++)
{
if (s[i] == '.' || s[i] == '/')
{
num[numCnt++] = temp * 1LL;
temp = 0;
}
else if (s[i] == '\0')
{
ip[id].len = temp;
break;
}
else
{
temp = temp * 10 + s[i] - '0';
}
}
}
else
{
for (int i = 1, temp = 0, numCnt = 1; ; i++)
{
if (s[i] == '.')
{
num[numCnt++] = temp * 1LL;
temp = 0;
}
else if (s[i] == '\0')
{
num[numCnt++] = temp * 1LL;
ip[id].len = (numCnt-1) * 8;
break;
}
else
{
temp = temp * 10 + s[i] - '0';
}
}
}
LL ans = 0;
for (int i = 1; i <= 4; i++)
{
ans = ans * 256 + num[i];
}
ip[id].ipNum = ans;
}
sort(ip + 1, ip + 1 + n);
LL mmax = -1;
int st = 0, en = n + 1;
ip[st].before = -1;
ip[st].next = en;
ip[en].before = st;
ip[en].next = -1;
for (int id = 1, prev = 0; id <= n; id++)
{
if (ip[id].ipNum > mmax)
{
ip[id].before = prev;
ip[id].next = en;
ip[prev].next = ip[en].before = id;
prev = id;
mmax = getMMax(ip[id]);
}
}
int pNow = ip[0].next;
while (pNow != en)
{
int p1 = pNow, p2 = ip[pNow].before;
if (p2 == 0)
pNow = ip[pNow].next;
else
{
if (ip[p1].len == ip[p2].len &&
(ip[p2].ipNum & (1LL << (32-ip[p2].len))) == 0 &&
(ip[p2].ipNum | (1LL << (32-ip[p2].len))) == ip[p1].ipNum)
{
ip[p1].before = ip[p2].before;
ip[ip[p1].before].next = p1;
ip[p1].ipNum = ip[p2].ipNum;
ip[p1].len --;
}
else
{
pNow = ip[pNow].next;
}
}
}
pNow = ip[0].next;
while (pNow != en)
{
ip[pNow].show();
pNow = ip[pNow].next;
}
return 0;
}
201812-4 数据中心
题目要求最长边最小的生成树。好吧,这就是一道kruskal MST题。
#include <bits/stdc++.h>
const int maxn = 50000;
const int maxm = 100000;
using namespace std;
struct tEdge
{
int u, v;
int t;
bool operator < (const tEdge &y) const
{
return t < y.t;
}
};
tEdge edge[maxm+10];
int cnt = 1;
int fa[maxn+10];
int getFa(int x)
{
if (x == fa[x])
return x;
return fa[x] = getFa(fa[x]);
}
int main()
{
int n, m, root;
scanf("%d%d%d", &n, &m, &root);
for (int i = 1, u, v, t; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &t);
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt++].t = t;
}
sort(edge + 1, edge + 1 + m);
for (int i = 1; i <= n; i++)
fa[i] = i;
int ans = -1;
for (int i = 1, temp = 0; temp != n - 1; i++)
{
int rx = getFa(edge[i].u), ry = getFa(edge[i].v);
if (rx != ry)
{
fa[rx] = ry;
temp ++;
ans = edge[i].t;
}
}
printf("%d\n", ans);
return 0;
}
201809
201809-3 元素选择器
题目要求写一个简易的CSS Selector。
首先用结构体\(<lev,label[],hasId,id[]>\)存储元素。其中\(lev\)表示元素在html树中的深度(这个是因为逻辑凌乱才加上的
接着用链式前向星存储html元素树。这里用一个栈\(rootStack\)方便找到新元素的父亲节点\(temp\)。
三种选择器都可以归结为第三种方式——后代选择器。
题目里已经给了算法:在匹配时,可以采用贪心的策略,除最后一级外,前面的部分都可以尽量匹配层级小的元素。写个dfs就好了。
注意标签不区分大小写,不可以直接用strcmp的。
字符串处理有点不方便。要熟练掌握%s,%[^],getchar,fgets,sscanf及相关函数。
#include <bits/stdc++.h>
const int maxn = 100;
const int maxm = 80; // max length of one element
using namespace std;
char line[maxm+10];
struct tElement
{
int lev;
char label[maxm+10];
bool hasId;
char id[maxm+10];
tElement()
{
hasId = false;
}
};
tElement element[maxn+10];
int to[maxn+10];
int nex[maxn+10];
int head[maxn+10];
char selector[maxm/2+10][maxm+10];
bool labelEqual(char s1[], char s2[])
{
if (strlen(s1) != strlen(s2))
return false;
for (int i = 0; s1[i] != '\0'; i++)
{
if (!((s1[i] == s2[i] || s1[i] + 32 == s2[i] || s1[i] - 32 == s2[i])))
return false;
}
return true;
}
priority_queue<int, vector<int>, greater<int> > q;
int num;
void dfs(int x, int cnt, int cnt0)
{
if (cnt != cnt0)
{
if ((selector[cnt][0] == '#' && element[x].hasId && strcmp(element[x].id, selector[cnt] + 1) == 0) ||
(selector[cnt][0] != '#' && labelEqual(element[x].label, selector[cnt])))
{
for (int i = head[x]; i != -1; i = nex[i])
{
int l = to[i];
dfs(l, cnt + 1, cnt0);
}
}
else
{
for (int i = head[x]; i != -1; i = nex[i])
{
int l = to[i];
dfs(l, cnt, cnt0);
}
}
}
else
{
if ((selector[cnt][0] == '#' && strcmp(element[x].id, selector[cnt] + 1) == 0) ||
(selector[cnt][0] != '#' && labelEqual(element[x].label, selector[cnt])))
{
q.push(x);
num ++;
}
for (int i = head[x]; i != -1; i = nex[i])
{
int l = to[i];
dfs(l, cnt, cnt0);
}
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
getchar();
stack<int> rootStack;
memset(head, -1, sizeof(head));
for (int i = 1, cnt = 0; i <= n; i++)
{
scanf("%[^\n]", line + 1);
getchar();
int dotNum = 0;
for (int j = 1; line[j] == '.'; j++)
{
dotNum ++;
}
element[i].lev = dotNum / 2;
if (!rootStack.empty())
{
while (element[rootStack.top()].lev >= dotNum / 2)
{
rootStack.pop();
}
int temp = rootStack.top();
to[cnt] = i;
nex[cnt] = head[temp];
head[temp] = cnt++;
}
rootStack.push(i);
sscanf(line + dotNum + 1, "%s", element[i].label);
if (line[dotNum + strlen(element[i].label) + 1] == ' ')
{
element[i].hasId = true;
sscanf(line + dotNum + strlen(element[i].label) + 3, "%s", element[i].id);
}
}
while (m--)
{
scanf("%[^\n]", line + 1);
getchar();
int iter = 1;
int cnt = 0;
while (true)
{
sscanf(line + iter, "%s", selector[++cnt]);
iter += strlen(selector[cnt]) + 1;
if (line[iter-1] == '\0')
break;
}
num = 0;
dfs(1, 1, cnt);
printf("%d", num);
while (num != 0)
{
printf(" %d", q.top());
q.pop();
num --;
}
printf("\n");
}
return 0;
}
转载于:https://www.cnblogs.com/acboyty/p/11229719.html