题还没补完
以下是牢骚：删了
现在只有六个。。。太恐怖了，我发现四星场我连300人的题都不会啊。
C：最短路加一维状态就好了叭。。嗯，一开始没看到输出的那句话 那个 "."也要输出，然后n，m看反了，这反人类啊这nm。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
struct node{
int u,t,p;
bool operator<(const node&rhs)const {
return p>rhs.p;
}
};
int x,n,m,l;
vector<int>g[];
int t[],p[],dis[][];
void Dijkstra(){
for(int i=;i<=n;i++)for(int j=;j<=x;j++)dis[i][j]=;
if(t[]>x)return;
dis[][t[]]=p[];
priority_queue<node>Q;
Q.push(node{,t[],p[]});
while (!Q.empty()){
node fr = Q.top();Q.pop();
if(dis[fr.u][fr.t]<fr.p)continue;
if(fr.t+t[fr.u]<=x&&fr.p+p[fr.u]<dis[fr.u][fr.t+t[fr.u]]){
dis[fr.u][fr.t+t[fr.u]]=fr.p+p[fr.u];
Q.push(node{fr.u,fr.t+t[fr.u],fr.p+p[fr.u]});
}
for(auto u:g[fr.u]){
if(fr.t+t[u]+l<=x&&fr.p+p[u]<dis[u][fr.t+t[u]+l]) {
dis[u][fr.t+t[u]+l]=fr.p+p[u];
Q.push(node{u, fr.t + t[u] + l, fr.p + p[u]});
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>x>>n>>m>>l;
int a,b;
for(int i=;i<=m;i++){
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=;i<=n;i++){
cin>>t[i]>>p[i];
}
Dijkstra();
if(dis[][x]==)cout<<"It is a trap."<<endl;
else cout<<dis[][x]<<endl;
}
D：签到，我写的很傻逼
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
string s1,s2,s;
int n,m,cnt=,vis[];
map<string,int>mp;
vector<int>g[];
set<int> st[];
void dfs(int v){
st[v].insert(v);
for(auto u:g[v]){
dfs(u);
for(auto tmp:st[u])
st[v].insert(tmp);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
while (n--){
cin>>s1>>s>>s>>s>>s2;
if(!mp.count(s1))mp[s1]=cnt++;
if(!mp.count(s2))mp[s2]=cnt++;
g[mp[s2]].push_back(mp[s1]);
}
for(int i=;i<cnt;i++){
if(!vis[i])
dfs(i);
}
while (m--){
cin>>s1>>s>>s>>s>>s2;
if(!mp.count(s1)||!mp.count(s2)){
cout<<"Pants on Fire"<<endl;
} else{
if(st[mp[s2]].count(mp[s1])){
cout<<"Fact"<<endl;
} else if(st[mp[s1]].count(mp[s2])){
cout<<"Alternative Fact"<<endl;
} else{
cout<<"Pants on Fire"<<endl;
}
}
}
}
G：现学的那个什么皮克公式。好神奇啊！虽然不知道为什么。然后仔细读题会发现他给你的点是按顺序的。算一下叉积就完了。可以百度 皮克公式呀qwq
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int n;
struct point{
ll x,y;
}p[];
ll cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
ll gcd(ll a,ll b){
a=abs(a);b=abs(b);
if(a==)return b;
if(b==)return a;
return __gcd(a,b);
}
int main(){
//ios::sync_with_stdio(false);
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%lld%lld",&p[i].x,&p[i].y);
ll S=,cnt=;
for(int i=;i<n;i++){
S+=cross(p[i],p[(i+)%n]);
}
S/=;
S=abs(S);
for(int i=;i<n;i++){
cnt+=gcd(p[i].x-p[(i+)%n].x,p[i].y-p[(i+)%n].y);
}
ll a = S-cnt/+;
printf("%lld\n",a);
}
/**
4
0 0
0 10
10 10
10 0 4
0 3
3 0
0 -1
-1 0
*/
F：哇上来我一看，这直接枚举不就完了吗！TLE ON TEST 8。说好的玄学复杂度呢呜呜呜 自闭。 后来想到会有大量重复的过程，，但是我学艺不精，写的最大流，就不会改了。。昨天看了题解！
哇！二分图匹配，然后每个点再做两次增广！用另外一个数组把一开始的存下来。草！这题竟该死的巧妙。匈牙利大法好哇。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+;
const int INF = 0x3f;
struct Edge{
int u,v,nxt;
Edge(int u=,int v=,int nxt=):u(u),v(v),nxt(nxt){}
}edge[*N];
int n,m,k,cnt;
int head[N],d[N],c[N];
void addEdge(int u,int v){
edge[++cnt]=Edge(u,v,head[u]);
head[u]=cnt;
}
int match[N],vis[N],tmp[N];
bool dfs(int u){
for(int i=head[u];~i;i=edge[i].nxt){
int v = edge[i].v;
if(vis[v])continue;
vis[v]=;
if(match[v]==-||dfs(match[v])){
match[v]=u;
return true;
}
}
return false;
}
void init(){
memset(head,-, sizeof(head));
cnt=;
}
int main(){
ios::sync_with_stdio(false);
init();
scanf("%d%d%d",&n,&m,&k);
int u,v;
for(int i=;i<=k;i++){
scanf("%d%d",&u,&v);
addEdge(u,v);
}
int mx=;
memset(match,-, sizeof(match));
for(int i=;i<=n;i++){
memset(vis,, sizeof(vis));
if(dfs(i))mx++;
}
memcpy(tmp,match,sizeof(match));
int ans =;
for(int i=;i<=n;i++){
int num=;
while (dfs(i)&&num<){
memset(vis,, sizeof(vis));
num++;
}
ans=max(ans,num);
memcpy(match,tmp, sizeof(tmp));
}
printf("%d\n",ans+mx);
}
I：签到
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int N = 3e5+;
int n,m;
int a[N],dp[N][];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;i++)cin>>a[i];
for(int i=m+;i<=n;i++){
dp[i][]=max(dp[i-m][],dp[i-m][])+a[i];
dp[i][]=max(dp[i-][],dp[i-][]);
}
cout<<max(dp[n][],dp[n][]);
}
K：签到
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int n,d,k;
struct Node{
string s;
int c;
bool operator < (const Node& a)const {
return c<a.c;
}
};
priority_queue<Node> q;
vector<string>ans;
int main(){
ios::sync_with_stdio(false);
cin>>n>>d>>k;
string s;int c;
while (n--){
cin>>s>>c;
q.push(Node{s,c});
}
int sum=;
while (!q.empty()&&sum<d){
sum+=q.top().c;
ans.push_back(q.top().s);
q.pop();
}
if(ans.size()>k||sum<d){
cout<<"impossible"<<endl;
} else{
cout<<ans.size()<<endl;
for(auto s:ans){
cout<<s<< ", YOU ARE FIRED!"<<endl;
}
}
}