1，签到：https://ac.nowcoder.com/acm/contest/78306/A
AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010];
long long sum;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
sum+=a[x];
}
cout<<sum;
}2.简单的数学：https://ac.nowcoder.com/acm/contest/78306/B
AC代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
long long ck=x+y;
ck=abs(x-y);
if(ck%3)
{
cout<<"No"<<endl;
continue;
}
cout<<"Yes"<<endl;
}
}3.分类讨论：https://ac.nowcoder.com/acm/contest/78306/C
注意特判当最后都可以0时，若在最后一位是1，答案是2，否则是1
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int t;
string n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
int a[10]={0};
for(int i=0;i<n.size();i++)
{
if(n[i]!='0') continue;
a[i]=1;
}
int x=0;
for(int i=n.size()-1;i>=0;i--)
{
x+=a[i]*(pow(10,n.size()-1-i));
}
if(x==0&&n[n.size()-1]!='1') cout<<1<<endl;
else if(x==0&&n[n.size()-1]=='1') cout<<2<<endl;
else cout<<x<<endl;
}
}4.暴力+差分：https://ac.nowcoder.com/acm/contest/78306/D
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int mod=998244353;
int n,m;
struct node{
int l,r;
}a[15];
long long cnt=0;
bool xun[11];
int c[100010];
int check()
{
memset(c,0,sizeof(c));
for(int i=1;i<=m;i++)
{
if(xun[i])
{
c[a[i].l]++;
c[a[i].r+1]--;
}
}
int x=0;
for(int i=1;i<=n;i++)
{
x+=c[i];
if(x<2) return 0;
}
return 1;
}
bool cmp(node a,node b)
{
return a.l<b.l;
}
void dfs(int c)
{
if(c>=m+1)
{
cnt+=check();
return;
}
xun[c]=1;
dfs(c+1);
xun[c]=0;
dfs(c+1);
return;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
a[i].l=x;
a[i].r=y;
}
sort(a+1,a+m+1,cmp);
dfs(1);
cout<<cnt;
}5.优先队列动态维护：https://ac.nowcoder.com/acm/contest/78306/E
首先一般的贪心是不对的，例如我一开始想把每一个B的时间（A到B的前缀和+B自己的时间）维护出来然后选前K个，但是因为你一个B选后，意味着它后面B的时间不是两个预先计算的简单相加。
因此，我们可以固定选了几个A，每一次计算用优先队列跟新即可（有点类似于DP求最大上升子序列固定最后一个元素的思想）
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,q,a[100010],b[100010],cnt;
int k;
int sum[100010];
void solve()
{
priority_queue<int> q;
long long ans=1e18;
long long summ=0;
long long st=0;
for(int i=1;i<=n;i++)
{
summ+=a[i];
q.push(b[i]);
st+=b[i];
if(q.size()>k)
{
st-=q.top();
q.pop();
}
if(q.size()==k) ans=min(ans,summ+st);
}
cout<<ans<<endl;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
while(q--)
{
cin>>k;
cnt=0;
solve();
}
}6。离散化+DP：https://ac.nowcoder.com/acm/contest/78306/F
每一个合法的序列都可以按左端点为第一关键字，右端为第二关键字升序排，可以用dp[k][i][j]表示，k表示目前按顺序选了k条，0--i的重复了>=2次，i-j的重复了1次，j-n的重复了0次，然后就是转移了。
下面是官方的题解以及代码：
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int mod = 998244353;
int dp[401][401][401];
void add(int& ret, int x) {
ret += x;
if(ret >= mod) ret -= mod;
}
void solve()
{
int n, m; cin >> n >> m;
vector<int> v;
vector<int> s(m + 1), t(m + 1);
for (int i = 1; i <= m; i++) {
cin >> s[i] >> t[i];
--s[i];
v.push_back(s[i]);
v.push_back(t[i]);
}
v.push_back(n), v.push_back(0);
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
n = v.size();
vector<pii> a(m + 1);
for (int i = 1; i <= m; i++) {
s[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin();
t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
a[i] = {s[i], t[i]};
}
sort(a.begin() + 1, a.end());
dp[0][0][0] = 1;
for (int k = 1; k <= m; k++) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (dp[k - 1][i][j] == 0) {
continue;
}
add(dp[k][i][j], dp[k - 1][i][j]);
if (a[k].first <= i) {
add(dp[k][max(i, min(j, a[k].second))][max(j, a[k].second)], dp[k - 1][i][j]);
}
}
}
}
cout << dp[m][n - 1][n - 1] << endl;
}
int main()
{
solve();
return 0;
}可能是我太菜了，有几个边界条件觉得比较奇怪，
1.最后出答案时dp[m][n-1][n-1]表示的不是[0,n-2]覆盖两次的次数吗？答案不是应该求[0,n-1]?
2.为什么有--s[i]？这里dp[k][i][j]中的i不是开区间吗，i的位置覆盖了1条，那么判断条件不应该是当前线段左端点<=i吗（我看很多大佬说是因为还有-1的缘故，但是我感觉按上面的定义不用-1）
3.为什么离散化加0，n两个端点？
不知道有没有大佬可以帮我解释下，谢谢qaq
