Directory
L1-3 Reading Room(20)
L1-6 divisible bachelor (20)
L1-8 Matrix A times B(15)
L2-2 rearrangement linked list(25)
L2-3 graph coloring problem (25) (DFS)
L3-1 Structure of binary search tree (30) (binary search tree + string)
L3-2 Sensen Express (30) (greedy + segment tree interval modification & amp; interval query)
L1-3 Reading Room (20)
Note: The start time may be 0, and the mp initialization needs to be -1
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n;
int nm,t1,h,m;
char c;
double cnt, sum;
int mp[N];
int main(){
scanf("%d", &n);
while(n--){
cnt=sum=0;
memset(mp,-1,sizeof(mp));//update start time
while (1) {
\t\t
scanf("%d %c", &nm, &c);
scanf("-:-", &h, &m);
if(nm==0)break;
\t\t\t
if(c=='E'){
if(mp[nm]==-1)continue;
else {
cnt + + ;
sum + =h*60 + m-mp[nm];
mp[nm]=-1;
}
}else{
mp[nm]=h*60 + m;
}
}if(cnt!=0)printf("%.lf %.lf\\
",cnt,1.0*(sum + 0.5)/cnt);
else printf("0 0\\
");
\t\t
}
return 0;
}
L1-6 Divisible Bachelor (20)
Analog division, such as 111/23, 1111/345, start division when 11…1>x
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn = 1e3 + 10;
int x,n,m=1;
int main(){
scanf("%d", &x);
while(m<x){
n + + ;m=m*10 + 1;
}while(1){
printf("%d",int(m/x));
n + + ;
if(m%x==0)break;
m=m%x*10 + 1;
}printf(" %d",n);
return 0;
}
L1-8 matrix A times B(15)
Note: Ca and Rb should output numbers
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int r1,c1,r2,c2,r3,c3;
int a[N][N],b[N][N],c;
int main(){
scanf("%d%d", &r1, &c1);
for(int i=1;i<=r1;i + + ){
for(int j=1;j<=c1;j++){
scanf("%d", &a[i][j]);
}
}
scanf("%d%d", &r2, &c2);
if(c1!=r2){
printf("Error: %d != %d",c1,r2);
return 0;
}
for(int i=1;i<=r2;i + + ){
for(int j=1;j<=c2;j++){
scanf("%d", &b[i][j]);
}
}
printf("%d %d\\
",r1,c2);
for(int i=1;i<=r1;i + + ){
for(int j=1;j<=c2;j++){
c=0;
for(int k=1;k<=c1;k++){
c + =a[i][k]*b[k][j];
}printf("%d",c);
if(j!=c2)printf(" ");
}if(i!=r1)printf("\\
");
}
\t
return 0;
}
L2-2 rearrangement list (25)
a[N]: Record the address of each node of the linked list before adjusting the order
b[N]: Record the address of each node of the linked list after adjusting the order
When outputting, you only need to know the address of the current node and the address of the next node, and the data can be queried according to the mapping relationship
Note: The given n nodes may not be continuous, so use cnt as a limit when changing the order and output
#include <bits/stdc++.h>
using namespace std;
const int N=1e5 + 10;
int idx,n;
struct node{
int data, nxt;
}mp[N];
int a[N],b[N];
int main(){
scanf("%d%d", &idx, &n);
for(int i=1;i<=n;i + + ){
int x; scanf("%d", &x);
scanf("%d%d", &mp[x].data, &mp[x].nxt);
}
int t = mp[idx].nxt;
int cnt=0;
a[ + + cnt]=idx;
while(t!=-1){
a[ + + cnt]=t;
t=mp[t].nxt;
}int front=1, rear=cnt;
cnt=0;
while(front<=rear){
b[ + + cnt]=a[rear--];
if(front<=rear)
b[ + + cnt]=a[front + + ];
}for(int i=1;i<=cnt;i ++ ){
if(i!=cnt)
printf(" d %d d\\
",b[i],mp[b[i]].data,b[i + 1]);
else
printf(" d %d -1",b[i],mp[b[i]].data);
}
return 0;
}
L2-3 Graph Coloring Problem (25) (DFS)
Undirected graph DFS search one by one
Note: Exactly k colors are required
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn = 1e3 + 10;
int n,m,k,x,y,q,vis[maxn],v[maxn];
vector<int>edge[maxn];
int f=1;
void dfs(int x){
vis[x]=1;
for(auto i:edge[x]){
if(v[i]==v[x]){
f=0; return;
}if(vis[i])continue;
//vis[i]=1;
dfs(i);
}
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i=1;i<=m;i + + ){
scanf("%d%d", &x, &y);
edge[x].push_back(y);
edge[y].push_back(x);
}
scanf("%d", &q);
while(q--){
set<int>ss;
for(int i=1;i<=n;i + + ){
scanf("%d", &v[i]);
ss.insert(v[i]);
}if(ss. size()!=k){
printf("No\\
");
continue;
}ss.clear();
f=1;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
dfs(i);
if(f)printf("Yes\\
");
else printf("No\\
");
}
return 0;
}
L3-1 Structure of binary search tree (30) (binary search tree + string)
.count(x) in the map: Find whether the key value x exists, return 1 if it exists, and return 0 if it does not exist
.find(“s”) in the string: Find whether “s” appears in the string, return the index if it appears, and return -1 if it does not appear
sscanf(s.c_str(),” “); string string input
Take logarithm: log(x)/log(2) logarithm of x with base 2
Note: It is necessary to judge whether the values q1 and q2 given in the title are in the given tree
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,rt,t,m;
int a[N],v[N];
map<int,int>ani;
void add(int id,int x){
if(!v[id]){
a[id]=x,v[id]=1;
ani[x]=id;
return;
}if(x<a[id])add(id*2,x);
else add(id*2 + 1,x);
}
int main(){
\t
scanf("%d%d", &n, &rt);
add(1,rt);
for(int i=2;i<=n;i + + ){
scanf("%d", &t);
add(1,t);
}
scanf("%d", &m);
\t
int q1,q2;
while(m--){
q1=q2=0;
scanf("%d", &q1);
string ss;
getline(cin,ss);
//cout<<ss<<endl;
int f=0;
if(!ani.count(q1)){
printf("No\\
");
continue;
}
if(ss.find("root")!=-1){
if(q1==rt)f=1;
}else if(ss.find("parent")!=-1){
sscanf(ss.c_str()," is the parent of %d", & amp;q2);
if(ani.count(q2) & amp; & amp;int(ani[q1])==(ani[q2]/2))f=1;
}else if(ss.find("left")!=-1){
sscanf(ss.c_str()," is the left child of %d", & amp;q2);
if(ani.count(q2) & amp; & amp;ani[q1]==ani[q2]*2)f=1;
}else if(ss.find("right")!=-1){
sscanf(ss.c_str()," is the right child of %d", & amp;q2);
if(ani.count(q2) & &ani[q1]==ani[q2]*2 + 1)f=-1;
}
else {
if(ss.find("siblings")!=-1){
sscanf(ss.c_str()," and %d are siblings", & amp;q2);
if(ani.count(q2) & &ani[q1]/2==ani[q2]/2)f=1;
}else if(ss.find("level")!=-1){
sscanf(ss.c_str()," and %d are on the same level", & amp;q2);
if(ani.count(q2)){
int tp1=log(ani[q1])/log(2);
int tp2=log(ani[q2])/log(2);
if(tp1==tp2)f=1;
}
}
}if(f)printf("Yes\\
");
else printf("No\\
");
}
return 0;
}
L3-2 Sensen Express (30) (greedy + line segment tree interval modification & interval query)
Greedy, if you want to get the maximum transport weight, you must greedily find the largest number of sections you don’t want to cross (because if they intersect, the goods transported on these two intersecting sections will jointly occupy the maximum transportation volume of the road)
Sort in ascending order of the right endpoint, (as shown in the figure below, taken from: Interval Coverage Problem – Greedy_There are n non-overlapping intervals, ask for the largest coverage area), use the line segment tree to maintain the minimum value of the interval, and then select each interval, put Query the minimum value (tmp) of this interval. If tmp>0, it can be transported. Modify updates the interval value minus x.
val: node i records the weight that can be transported from i-1 to i, updated to 0
minv: record the minimum shipping weight of the subtree
query: Interval query whether the minimum value from the start point to the end point is >0
modify: interval modification t mark lowered minus the minimum value
The node only needs to record the mark and the minimum value, no need for info
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson id*2,l,m
#define rson id*2 + 1,m + 1,r
const int N = 1e5 + 5;
int n, q;
ll sum;
struct s_t{
int s,t,c;
bool operator<(const s_t & b)const{
//if(c!=b.c)return c<b.c;
if(t!=b.t) return t<b.t;
return s<b.s;
}
}a[N];
//val: node i records the weight that can be transported from i-1 to i, and updates it to 0
//minv: record the minimum transport weight of the subtree
//query: Interval query whether the minimum value from the start point to the end point is >0
//modify: interval modification t mark lowered minus the minimum value
//The node only needs to record the mark and the minimum value without info
struct node{
int t;
int minv;
}seg[N*4];
void update(int id){
seg[id].minv=min(seg[id*2].minv,seg[id*2 + 1].minv);
}
void settag(int id,int t){
seg[id].minv + =t;
seg[id].t + =t;
}
void pushdown(int id){
if(seg[id].t!=0){
settag(id*2,seg[id].t);
settag(id*2 + 1,seg[id].t);
seg[id].t=0;
}
}
void build(int id, int l, int r){
if(l==r){
scanf("%d", & amp;seg[id].minv);
seg[l].t=0;
//printf("seg[%d].minv:%d\\
",l,seg[l].minv);
return;
}int m=(l + r)/2;
build(lson);
build(rson);
update(id);
//printf("seg[%d].minv:%d\\
",l,seg[l].minv);
}
int query(int id, int l, int r, int ql, int qr){
//printf("[%d,%d]\\
",l,r);
//printf("seg[%d].minv:%d\\
",id,seg[id].minv);
if(ql==l & amp; & amp;qr==r) {
\t\t
return seg[id].minv;
}
pushdown(id);
int m=(l + r)/2;
if(qr<=m) return query(lson,ql,qr);
else if(ql>m) return query(rson,ql,qr);
else return min(query(lson,ql,m),query(rson,m+1,qr));
}
void modify(int id, int l, int r, int ml, int mr, int t){
if(ml==l & amp; & amp; mr==r){
settag(id,t);
return;
}pushdown(id);
int m=(l + r)/2;
if(mr<=m)modify(lson,ml,mr,t);
else if(ml>m) modify(rson,ml,mr,t);
else modify(lson,ml,m,t),modify(rson,m+1,mr,t);
update(id);
}
int main() {
scanf("%d %d", &n, &q);
build(1, 1, n-1);
for(int i=1;i<=q;i + + ){
int s,t;
scanf("%d%d", &s, &t);
if(s>t)swap(s,t);
a[i]=(s_t){s + 1,t,t-s};
}sort(a + 1,a + q + 1);
for(int i=1;i<=q;i + + ){
int tmp=query(1,1,n-1,a[i].s,a[i].t);
//printf("a[%d].s:%d .t:%d tmp:%d\\
",i,a[i].s,a[i].t,tmp);
if(tmp>0){
sum + =tmp;
modify(1,1,n-1,a[i].s,a[i].t,-tmp);
}
}printf("%lld",sum);
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill tree Home pageOverview 41893 people are studying systematically