队友写的。 好像水水的。
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 998244353
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-5;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=1000000+10,maxn=1000000+10,inf=0x3f3f3f3f;
ll dp[200][2];
int main()
{
int l,k;scanf("%d%d",&l,&k);
dp[1][1]=dp[k][1]=1;
for(int i=1;i<=l;i++)
{
dp[i+1][0]+=dp[i][1];
dp[i+1][1]+=dp[i][0];
dp[i+k][1]+=dp[i][0];
}
ll ans=0;
for(int i=1;i<=l;i++)ans+=dp[i][1];
printf("%lld\n",ans);
return 0;
}
/********************
********************/
View Code
队友写的。
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize(4)
//#pragma GCC optimize("unroll-loops")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define fi first
#define se second
#define db double
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 998244353
#define ld long double
//#define C 0.5772156649
//#define ls l,m,rt<<1
//#define rs m+1,r,rt<<1|1
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define ull unsigned long long
//#define base 1000000000000000000
#define fin freopen("a.txt","r",stdin)
#define fout freopen("a.txt","w",stdout)
#define fio ios::sync_with_stdio(false);cin.tie(0)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}
inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
template<typename T>inline T const& MAX(T const &a,T const &b){return a>b?a:b;}
template<typename T>inline T const& MIN(T const &a,T const &b){return a<b?a:b;}
inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;}
using namespace std;
const ull ba=233;
const db eps=1e-5;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100000+10,maxn=1000000+10,inf=0x3f3f3f3f;
ll a[N];
int main()
{
ll n,t;scanf("%lld%lld",&n,&t);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
ll ma=0,sum=0;
for(int i=1;i<=n;i++)
{
ma=max(ma,a[i]);
sum=sum+a[i];
if(t<sum)printf("%d\n",1);
else
{
ll te=(t-sum)/ma+2;
printf("%lld\n",te);
}
}
return 0;
}
/********************
********************/
View Code
dfs暴力枚举两两组合的情况， 枚举选第一个没被选的和枚举的组合， 这样能把复杂度降到最低。
然后答案一遍加入一遍更新， 好像我常数扣的有点厉害。 复杂度是15 * 13 * 11 * ... * 3
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 16 + 7;
const int M = 2000 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
struct Point {
int x, y;
} p[N];
int X[16][16], Y[16][16], all;
int num[4007][4007];
int n, cnt[1 << 16], who[1 << 16];
int ans, tmp;
vector<int> go[1 << 16];
inline void change(int x, int y, int op) {
x += 2000, y += 2000;
if(op == 1) tmp += num[x][y];
else tmp -= num[x][y] - 1;
num[x][y] += op;
}
void dfs(int S) {
if(cnt[S] + 2 > n) {
ans = max(ans, tmp);
return;
}
for(int i = 1; i < SZ(go[S]); i++) {
change(X[go[S][0]][go[S][i]], Y[go[S][0]][go[S][i]], 1);
dfs(S | (1 << go[S][0]) | (1 << go[S][i]));
change(X[go[S][0]][go[S][i]], Y[go[S][0]][go[S][i]], -1);
}
}
int main() {
for(int i = 1; i < (1 << 16); i++)
cnt[i] = cnt[i - (i & -i)] + 1;
scanf("%d", &n);
all = n / 2;
for(int i = 0; i < n; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
X[i][j] = p[i].x - p[j].x;
Y[i][j] = p[i].y - p[j].y;
int gcd = __gcd(X[i][j], Y[i][j]);
X[i][j] /= gcd;
Y[i][j] /= gcd;
if(X[i][j] < 0) X[i][j] = -X[i][j], Y[i][j] = -Y[i][j];
// printf("%d %d: %d %d\n", i, j, X[i][j], Y[i][j]);
}
}
for(int i = 0; i < (1 << n); i++)
for(int k = 0; k < n; k++)
if(!(i >> k & 1)) go[i].push_back(k);
dfs(0);
printf("%d\n", ans);
return 0;
}
/*
*/
View Code
I - Starting a Scenic Railroad Service
队友写的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<iostream>
#include<stack>
#include<string>
#include<map>
using namespace std;
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mst(x,a) memset(x,a,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define CLOSE ios::sync_with_stdio(false)
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define cl(x) x.clear()
const int mod = 1000000007;
const int N = 200010;
const int INF=0x3f3f3f3f;
void MOD(ll &a){if(a>=mod) a-=mod;}
void MOD(ll &a,ll c){if(a>=c) a-=c;}
void ADD(ll &a,ll b){ a+=b; MOD(a);}
void ADD(ll &a,ll b,ll c){a+=b;MOD(a,c);}
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;}
ll qpow(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c;b/=2;}return ans;}
int n;
int x[N],y[N],B[N];
struct seg{
int l,r;
}a[N],b[N];
bool cmp1(seg a,seg b){
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
bool cmp2(seg a,seg b){
if(a.r==b.r) return a.l<b.l;
return a.r<b.r;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
y[i]--;
B[x[i]]++; B[y[i]+1]--;
a[i].l=x[i]; a[i].r=y[i];
b[i].l=x[i]; b[i].r=y[i];
}
sort(a+1,a+1+n,cmp1);
sort(b+1,b+1+n,cmp2);
int ans1=0,ans2=0;
for(int i=1;i<=100001;i++){
B[i]+=B[i-1]; ans2=max(ans2,B[i]);
}
//a sort by l b sort by r
for(int i=1;i<=n;i++){
int tmp=n;
int l=1,r=n+1;
while(l+1<r){
int m=l+r>>1;
if(a[m].l>y[i]) r=m;
else l=m;
}
tmp-=n-r+1;
l=0,r=n;
while(l+1<r){
int m=l+r>>1;
if(b[m].r<x[i]) l=m;
else r=m;
}
tmp-=l;
ans1=max(ans1,tmp);
}
printf("%d %d\n",ans1,ans2);
}
/*
*/
View Code
感觉是比较常规的套路题。
把边(u, v, w)反转以后如果 dis[ 1 ][ v ] + dis[ 2 ][ u ] + w < 最短路则是happy， 这里有个问题就是反转之后1到不了v， 但是反转前到到的了，
那么dis[ 1 ][ v ] 就不是INF， 但是通过分析我们能发现这不影响结果。
然后就是 sad 和 soso， 这个对 1 到 2 之间的最短路图求个桥就好了，看看反转的是不是桥。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
int n, m, a[N], b[N], c[N];
LL dis[2][N];
bool flag[N];
struct node {
LL d;
int to, id;
bool operator < (const node& rhs) const {
return d > rhs.d;
}
};
vector<node> G[N], rG[N], sG[N];
priority_queue<node> que;
void Dij(int S, LL dis[N]) {
dis[S] = 0;
que.push(node{0, S, 0});
while(!que.empty()) {
int u = que.top().to;
LL d = que.top().d; que.pop();
if(d > dis[u]) continue;
for(auto& t : G[u]) {
if(d + t.d < dis[t.to]) {
dis[t.to] = d + t.d;
que.push(node{dis[t.to], t.to, 0});
}
}
}
}
void Dij2(int S, LL dis[N]) {
dis[S] = 0;
que.push(node{0, S, 0});
while(!que.empty()) {
int u = que.top().to;
LL d = que.top().d; que.pop();
if(d > dis[u]) continue;
for(auto& t : rG[u]) {
if(d + t.d < dis[t.to]) {
dis[t.to] = d + t.d;
que.push(node{dis[t.to], t.to, 0});
}
}
}
}
int dfn[N], low[N], idx;
bool in[N];
void tarjan(int u, int fa) {
in[u] = true; ++idx;
dfn[u] = low[u] = idx;
for(node& t : sG[u]) {
int v = t.to;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(dfn[u] < low[v]) flag[t.id] = true;
} else if(in[v]) {
low[u] = min(low[u], dfn[v]);
}
}
in[u] = false;
}
int main() {
memset(dis, INF, sizeof(dis));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
G[a[i]].push_back(node{c[i], b[i], i});
rG[b[i]].push_back(node{c[i], a[i], i});
}
Dij(1, dis[0]);
Dij2(2, dis[1]);
LL mn = dis[0][2];
if(mn != INF) {
for(int i = 1; i <= n; i++) {
for(node t : G[i]) {
if(t.d + dis[0][i] + dis[1][t.to] == mn) {
sG[i].push_back(t);
sG[t.to].push_back(node{t.d, i, t.id});
}
}
}
tarjan(1, 0);
for(int i = 1; i <= m; i++) {
if(dis[0][b[i]] + dis[1][a[i]] + c[i] < mn) {
puts("HAPPY");
} else {
if(flag[i]) puts("SAD");
else puts("SOSO");
}
}
} else {
for(int i = 1; i <= m; i++) {
if(dis[0][b[i]] + dis[1][a[i]] + c[i] < mn) {
puts("HAPPY");
} else {
puts("SAD");
}
}
}
return 0;
}
/*
*/
View Code
赛后补题**********************************************************************************************************************************************
G - Rendezvous on a Tetrahedron
训练结束半个多小时才码出来。。。 把四面体展开， 然后暴力的取找到它最后的位置在哪里， 好像有更方便的方法， 我写得好麻烦啊啊。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
struct Point {
double x, y;
void print() {
printf("%.3f %.3f ^^\n", x, y);
}
Point(double x = 0, double y = 0) : x(x), y(y) { }
};
typedef Point Vector;
int dcmp(double x) {
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
}
Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}
Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}
Point operator * (Vector A, double p) {return Point(A.x * p, A.y * p);}
Point operator / (Vector A, double p) {return Point(A.x / p, A.y / p);}
bool operator < (const Vector &A, const Vector &B) {return A.y < B.y || (A.y == B.y && A.x < B.x);}
bool operator == (const Vector &A, const Point &B) {return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0;}
double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}
double Length(Vector A) {return sqrt(Dot(A, A));}
double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Length(A) / Length(B));}
double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}
double Area2(Point A, Point B, Point C) {return Cross(B - A, C - A);}
Vector Rotate(Vector A, double rad) {
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
double GetLineIntersectionTime(Point P, Vector v, Point Q, Vector w) {
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return t;
}
double dist(const Point& a, const Point &b) {
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
bool isPointOnSegment(const Point &p, const Point &a1, const Point &a2)
{
if(dcmp(Cross(a1-p,a2-p))) return 0;
else if(dcmp(p.x-min(a1.x,a2.x))>=0&&dcmp(p.x-max(a1.x,a2.x))<=0
&&dcmp(p.y-min(a1.y,a2.y))>=0&&dcmp(p.y-max(a1.y,a2.y))<=0) return 1;
else return 0;
}
int isPointInPolygon(Point p, Point *poly, int n) {
int wn = 0;
for(int i = 0; i < n; i++) {
if(isPointOnSegment(p, poly[i], poly[(i+1)%n])) return -1; //在边界上
int k = dcmp(Cross(poly[(i+1)%n]-poly[i], p-poly[i]));
int d1 = dcmp(poly[i].y-p.y);
int d2 = dcmp(poly[(i+1)%n].y-p.y);
if(k>0 && d1<=0 && d2>0) wn++;
if(k<0 && d2<=0 && d1>0) wn--;
}
if(wn != 0) return 1; //内部
return 0; //外部
}
Point A2 = Point(0, 0);
Point A3 = Point(2, 0);
Point A1 = Point(1, sqrt(3.0));
Point D = (A1 + A2) / 2;
Point B = (A1 + A3) / 2;
Point C = (A2 + A3) / 2;
Point poly1[] = {A1, D, B};
Point poly2[] = {D, C, B};
Point poly3[] = {D, A2, C};
Point poly4[] = {B, C, A3};
bool isA12(Point x) {
return isPointOnSegment(x, A1, A2);
}
bool isA23(Point x) {
return isPointOnSegment(x, A2, A3);
}
bool isA31(Point x) {
return isPointOnSegment(x, A3, A1);
}
int belong(Point x) {
if(isPointInPolygon(x, poly1, 3) == 1) return 1;
if(isPointInPolygon(x, poly2, 3) == 1) return 2;
if(isPointInPolygon(x, poly3, 3) == 1) return 3;
if(isPointInPolygon(x, poly4, 3) == 1) return 4;
}
Point dfs(Point p, Vector v, double len) {
if(isA12(p)) {
double t1 = GetLineIntersectionTime(p, v, A2, A3 - A2);
double t2 = GetLineIntersectionTime(p, v, A1, A3 - A1);
Point nxtp;
if(dcmp(t1) > 0 && (dcmp(t2) <= 0 || dcmp(t1) > 0 && t1 < t2)) {
nxtp = p + (v * t1);
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = C * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
} else {
nxtp = p + v * t2;
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = B * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
}
} else if(isA23(p)) {
double t1 = GetLineIntersectionTime(p, v, A1, A1 - A2);
double t2 = GetLineIntersectionTime(p, v, A1, A1 - A3);
Point nxtp;
if(dcmp(t1) > 0 && (dcmp(t2) <= 0 || dcmp(t1) > 0 && t1 < t2)) {
nxtp = p + v * t1;
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = D * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
} else {
nxtp = p + v * t2;
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = B * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
}
} else if(isA31(p)) {
double t1 = GetLineIntersectionTime(p, v, A2, A2 - A1);
double t2 = GetLineIntersectionTime(p, v, A2, A2 - A3);
Point nxtp;
if(dcmp(t1) > 0 && (dcmp(t2) <= 0 || dcmp(t1) > 0 && t1 < t2)) {
nxtp = p + v * t1;
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = D * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
} else {
nxtp = p + v * t2;
double gg = dist(p, nxtp);
if(dcmp(len - gg) < 0) {
return p + (v / Length(v)) * len;
} else {
nxtp = C * 2.0 - nxtp;
v = Rotate(v, PI);
return dfs(nxtp, v, len - gg);
}
}
}
}
Point read() {
char s[10];
double d, l;
scanf("%s%lf%lf", s, &d, &l);
if(s[0] == 'C' && s[1] == 'D') {
Point startp = A2;
Vector startv = Rotate(C - A2, d / 180 * PI);
return dfs(startp, startv, l);
} else if(s[0] == 'D' && s[1] == 'B') {
Point startp = A1;
Vector startv = Rotate(D - A1, d / 180 * PI);
return dfs(startp, startv, l);
} else {
Point startp = A3;
Vector startv = Rotate(B - A3, d / 180 * PI);
return dfs(startp, startv, l);
}
}
int main() {
Point Point1 = read();
Point Point2 = read();
if(belong(Point1) == belong(Point2)) puts("YES");
else puts("NO");
return 0;
}
/*
*/
View Code
不会写， 但是看了题解觉得好有道理啊啊啊， 我怎么没想到呢。
我们把t[ i ] == s[ i ]的位置的颜色保留， 把颜色不同的当成没有颜色就好了。
我们定义dp[ i ] 表示把 1 - i 全部染成对应颜色所需要的次数。
我们把 t 中连续相同的一段看成一个整体。变成 WBWBWB的形式， 如果长度为 m 则答案为 (m / 2) + 1
如果t[ i ] == s[ i ] dp[ i ] = dp[ i - 1]
否则 dp[ i ] = min(dp[ j ] + (sum[ i ] - sum[ j + 1 ]) / 2 + 1)
很显然能发现能用单调队列优化。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;
const int N = 5e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
int n, k, head, rear, sum[N], que[N];
int dp[N];
char s[N], t[N];
int main() {
scanf("%d%d", &n, &k);
scanf("%s%s", s + 1, t + 1);
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (t[i] != t[i - 1]);
head = 1, rear = 0;
dp[0] = 0;
que[++rear] = 0;
for(int i = 1; i <= n; i++) {
if(t[i] == s[i]) {
dp[i] = dp[i - 1];
} else {
while(head <= rear && i - que[head] > k) head++;
dp[i] = dp[que[head]] + (sum[i] - sum[que[head] + 1] + 1) / 2 + 1;
}
while(head <= rear && 2*dp[i] - sum[i + 1] <= 2*dp[que[rear]] - sum[que[rear] + 1]) rear--;
que[++rear] = i;
}
printf("%d\n", dp[n]);
return 0;
}
/*
*/
View Code