题意：给出两个长度为$n$的数组$A$和$B$和一个整数$K$，构造一个长度为$n$的数组，满足第$i$位是$A_i$或$B_i$且相邻两数绝对值差不超过$K$
解法：考虑$dp$，定义$dpa[i]$：$A$的第$i$位数字能否作为构造数组的第$i$位，能为1，否为0，同理定义$dpb[i]$，则转移方程为：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 2e5 + 5;
int n,k,a[maxn],b[maxn];
bool dpa[maxn],dpb[maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
cin>>b[i];
}
dpa[1] = dpb[1] = true;
for(int i=1;i<=n;++i){
if(abs(a[i]-a[i-1])<=k) dpa[i] |= dpa[i-1];
if(abs(a[i]-b[i-1])<=k) dpa[i] |= dpb[i-1];
if(abs(b[i]-a[i-1])<=k) dpb[i] |= dpa[i-1];
if(abs(b[i]-b[i-1])<=k) dpb[i] |= dpb[i-1];
}
if(dpa[n]||dpb[n]) cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
|
题意：对于多项式乘法$A(i)*B(i)=C(i)$，给出$A(i), C(i)$的每一项系数（不为0），求$B(i)$的每一项系数
解法：模拟长除法即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 2e5 + 5;
int n,m;
ll a[1005],b[1005],c[1005];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<=n;++i){
cin>>a[i];
}
for(int i=0;i<=m+n;++i){
cin>>c[i];
}
for(int i=m;i>=0;--i){
ll d = c[i+n]/a[n];
b[i] = d;
int cnt = n;
for(int j=i+n;j>=0;--j){
c[j] -= d * a[cnt--];
}
}
for(int i=0;i<=m;++i){
cout<<b[i]<<" ";
}
cout<<"\n";
return 0;
}
|
题意：给出N个巧克力和M个盒子的长宽，每个盒子最多只能装一个巧克力，问能否将N个巧克力全部装入盒子里（能装入盒子的条件是巧克力的长$\le$盒子的长，且巧克力的宽$\le$盒子的宽）
解法：将巧克力和盒子合并在一起考虑，以宽度降序排序，宽度相同的盒子在前。开一个multiset，遍历整个序列，如果是盒子则将盒子的长加入multiset，否则在multiset中二分找到第一个不小于该巧克力长的盒子长，删去它，如果找不到，则No，如果能完成全部遍历则Yes
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 2e5 + 5;
int n,m;
pair<int,int> ab[maxn],cd[maxn];
struct node{
int x,y,id;
}a[maxn<<1];
bool cmp(node &x1,node &x2){
if(x1.x!=x2.x) return x1.x > x2.x;
if(x1.y!=x2.y) return x1.y > x2.y;
return x1.id < x2.id;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>ab[i].first;
for(int i=1;i<=n;++i) cin>>ab[i].second;
for(int i=1;i<=m;++i) cin>>cd[i].first;
for(int i=1;i<=m;++i) cin>>cd[i].second;
for(int i=1;i<=n;++i){
a[i].id = 1;
a[i].x = ab[i].first;
a[i].y = ab[i].second;
}
for(int i=1;i<=m;++i){
a[i+n].id = 0;
a[i+n].x = cd[i].first;
a[i+n].y = cd[i].second;
}
sort(a+1,a+1+n+m,cmp);
multiset<int> se;
for(int i=1;i<=n+m;++i){
if(a[i].id==0){
se.insert(a[i].y);
}else{
auto it = se.lower_bound(a[i].y);
if(it==se.end()) return cout<<"No\n",0;
se.erase(it);
}
}
cout<<"Yes\n";
return 0;
}
|
题意：给出一个N个点M条边的有向图，问满足以下条件的节点的个数：从该点出发能够进入无限循环
解法：显然所有SCC里的点都满足要求，除此之外，所有能到达一个[节点数大于1的SCC]的节点也满足要求，因此考虑Tarjan缩点后反向建边然后从所有[节点数大于1的SCC]开始dfs即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 2e5 + 5;
int n,m;
struct Edge{
int u,v,next;
}e[maxn];
std::vector<int> ee[maxn];
int gcnt,head[maxn];
inline void init_graph(){
gcnt=0;
memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v){
e[gcnt]=Edge{u,v,head[u]};
head[u]=gcnt++;
}
int low[maxn],dfn[maxn],sta[maxn],color[maxn],vis[maxn],top,scc,deep;
int cnt[maxn];
void tarjan(int u){
vis[sta[++top]=u]=1;
low[u]=dfn[u]=++deep;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
vis[u]=0;
color[u]=++scc;
while(sta[top]!=u){
color[sta[top]]=scc;
vis[sta[top--]]=0;
}
top--;
}
}
bool ma[maxn];
void dfs(int u){
for(auto &v:ee[u]){
if(!ma[v]){
ma[v] = 1;
dfs(v);
}
}
}
int main(){
init_graph();
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
addedge(u,v);
}
for(int i=1;i<=n;++i){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=n;++i) cnt[color[i]]++;
for(int u,v,i=0;i<m;++i){
u = color[e[i].u];
v = color[e[i].v];
if(u!=v){
ee[v].emplace_back(u);
}
}
for(int i=1;i<=scc;++i){
if(!ma[i] && cnt[i]>1) ma[i]=1, dfs(i);
}
int ans = 0;
for(int i=1;i<=scc;++i){
if(ma[i]) ans += cnt[i];
}
printf("%d\n",ans);
return 0;
}
|