A - Buy a Pen（模拟）
题意：输入红笔r元，绿笔g元，蓝笔b元，不喜欢c笔，求最少花多少钱能买到一支笔
分析：比较除了c笔之外的两根笔，取最小值
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int r,g,b;cin>>r>>g>>b;
string c;cin>>c;
if(c[0]=='B')cout<<min(r,g);
else if(c[0]=='R')cout<<min(g,b);
else cout<<min(r,b);
return 0;
}B - Right Triangle（数学，模拟）
题意：给定三个坐标，求三个坐标俩俩相连围成的三角形是否为直角三角形，如果是输出yes，否则no
分析：先算出每条边，因为第三条边一定大于两边之和，所以再给三条边排序，如果a^2+b^2=c^2就说明是直角三角形
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int xa,ya,xb,yb,xc,yc;cin>>xa>>ya>>xb>>yb>>xc>>yc;
ll a[5];
a[1]=(ya-yb)*(ya-yb)+(xa-xb)*(xa-xb);
a[2]=(ya-yc)*(ya-yc)+(xa-xc)*(xa-xc);
a[3]=(yb-yc)*(yb-yc)+(xb-xc)*(xb-xc);
sort(a+1,a+4);
if(a[1]+a[2]==a[3])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}C - Sum = 0（贪心）
题意：给定n个区间，如果存在x1,x2,...xn（li<=xi<=ri&&∑xi=0)输出yes和序列，否则no
分析：先令所有数字为右区间，如果（最大的数字）小于0，那么永远都不可能变成0，如果（最小的数字）大于0，那么永远都不可能变成0，再从1遍历到n，判断数字是否要向左移动（向左移动了sum就会变小）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;cin>>n;
ll l[n+10],r[n+10];
int a[n+10];
ll sum=0;
for(int i=1;i<=n;i++){
cin>>l[i]>>r[i];
sum+=r[i];
}
if(sum<0)cout<<"No"<<endl;
else{
for(int i=1;i<=n;i++){
if(sum>r[i]-l[i]){
sum-=(r[i]-l[i]);
r[i]=l[i];
}
else if(sum==0)break;
else{
r[i]-=sum;
sum=0;
}
}
if(sum>0){
cout<<"No"<<endl;return 0;
}
cout<<"Yes"<<endl;
for(int i=1;i<=n;i++){
cout<<r[i]<<" ";
}
}
}D - Shortest Path 3（最短路dijkstra）
题意：有n个点和m条边，每个顶点的权重为ai，每条边的边权重bi，找出顶点1到顶点i的路径的最小权重
分析：带夫
代码：
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
ll n, m, cnt;
ll vis[1000005];
ll dis[1000005];
ll head[1000005];
ll a[1000005];
struct edge
{
ll to; // 点
ll w;
ll next;
} edg[1000005];
struct node
{
ll dis;
ll pos;
bool operator<(const node &x) const // 堆优化
{
return x.dis < dis;
}
};
void add_edge(ll u, ll v, ll w)
{
cnt++;
edg[cnt].w = w;
edg[cnt].to = v;
edg[cnt].next = head[u];
head[u] = cnt;
}
priority_queue<node> q;
void dijkstra()
{
node nod;
nod.dis = 0;
nod.pos = 1;
q.push(nod);
while (!q.empty())
{
node tmp = q.top(); // 提取队首元素
q.pop();
if (vis[tmp.pos])
continue;
vis[tmp.pos] = 1;
// int W = a[tmp.pos];
for (int i = head[tmp.pos]; i; i = edg[i].next)
{
int to = edg[i].to;
if (dis[to] > dis[tmp.pos] + edg[i].w + a[to])
{
dis[to] = dis[tmp.pos] + edg[i].w + a[to];
if (!vis[to])
{
node no;
no.dis = dis[to];
no.pos = to;
q.push(no);
}
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
memset(dis, 0x7f7f7f7f, sizeof(dis)); // 起点到某点的最短路大小
memset(vis, 0, sizeof(vis));
dis[1] = 0; // 点s到自己的距离0
for (int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
add_edge(v, u, w);
}
dis[1] = a[1];
dijkstra();
for (int i = 2; i <= n; i++)
{
cout << dis[i] << " ";
}
return 0;
}E - Count Arithmetic Subsequences（dp）
题意：给定一个数组A，求长度为k的A的子序列中等差数列的个数。模为998244353。如果两个子序列取自不同的位置，即使它们作为序列是相等的，也是有区别的。
分析：设dpi[d]为以i为结尾公差为d的长度为k的个数。k的范围为[1,n]
当len为1时，d为0；当len为2时，d为两数之差
dpi[ai-aj]=(dpj[ai-aj](j的范围为[2,n-1]
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100;
const ll mod=998244353;
ll a[N],ans[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i][1][0]=1;//长度为1为本身
ans[1]++;ans[1]%=mod;
for(int j=1;j<i;j++){//长度为2
dp[i][2][a[i]-a[j]]++;
}
ans[2]+=i-1;ans[2]%=mod;
}
for(int k=3;k<=n;k++){//枚举长度
for(int i=3;i<=n;i++){//i为结尾
for(int j=i-1;j>=1;j--){//i前面
dp[i][k][a[i]-a[j]]+=dp[j][k-1][a[i]-a[j]]%mod;
dp[i][k][a[i]-a[j]]%=mod;
ans[k]+=dp[j][k-1][a[i]-a[j]]%mod;
ans[k]%=mod;
}
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
