2013-2014 ACM-ICPC, NEERC, Eastern Subregional Contest PART (8/10)
\(A.Podracing\)
首先枚举各个折现上的点，找出最小宽度，然后找每个存在摄像头的\(y\)值，在这个\(y\)坐标下找到最大间隔，和答案取\(max\)即可
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
int n,m,q;
pair<double,double> lb[MAXN],rb[MAXN],cam[MAXN];
double res = 3e9+7;
void checkbod(){
for(int i = 1; i <= n; i++){
int p = lower_bound(rb+1,rb+1+m,lb[i],[](const pair<double,double> A, const pair<double,double> B){
return A.second<B.second;
}) - rb;
if(rb[p].second==lb[i].second){
res = min(res,double(rb[p].first-lb[i].first));
continue;
}
auto p1 = rb[p-1], p2 = rb[p];
double x = p1.first+(p2.first-p1.first)*(lb[i].second-p1.second)/(p2.second-p1.second);
res = min(res,x-lb[i].first);
}
for(int i = 1; i <= m; i++){
int p = lower_bound(lb+1,lb+1+n,rb[i],[](const pair<double,double> A, const pair<double,double> B){
return A.second<B.second;
}) - lb;
if(lb[p].second==rb[i].second){
res = min(res,double(rb[i].first-lb[p].first));
continue;
}
auto p1 = lb[p-1], p2 = lb[p];
double x = p1.first+(p2.first-p1.first)*(rb[i].second-p1.second)/(p2.second-p1.second);
res = min(res,rb[i].first-x);
}
}
void check(vector<int> &vec){
if(vec.empty()) return;
double y = cam[vec.back()].second;
if(y>lb[n].second||y<lb[1].second) return;
double lbord,rbord;
int p;
p = lower_bound(lb+1,lb+1+n,make_pair(0,y),[](const pair<double,double> A,const pair<double,double> B){
return A.second < B.second;
}) - lb;
if(lb[p].second==y) lbord = lb[p].first;
else{
auto p1 = lb[p-1], p2 = lb[p];
lbord = p1.first+(p2.first-p1.first)*1.0*(y-p1.second)/(p2.second-p1.second);
}
p = lower_bound(rb+1,rb+1+m,make_pair(0,y),[](const pair<double,double> A,const pair<double,double> B){
return A.second < B.second;
}) - rb;
if(rb[p].second==y) rbord = rb[p].first;
else{
auto p1 = rb[p-1], p2 = rb[p];
rbord = p1.first+(p2.first-p1.first)*1.0*(y-p1.second)/(p2.second-p1.second);
}
vector<double> xpos;
xpos.emplace_back(lbord);
sort(vec.begin(),vec.end(),[](int A, int B){
return cam[A].first < cam[B].first;
});
for(int ID : vec){
if(cam[ID].first<xpos.back()) continue;
xpos.emplace_back(cam[ID].first);
}
while(xpos.back()>rbord) xpos.pop_back();
xpos.emplace_back(rbord);
double maxwidth = 0;
for(int i = 1; i < (int)xpos.size(); i++) maxwidth = max(maxwidth,xpos[i]-xpos[i-1]);
res = min(res,maxwidth);
}
void checkcam(){
sort(cam+1,cam+1+q,[](const pair<double,double> A, const pair<double,double> B){ return A.second < B.second; });
int cur = 1;
vector<int> vec;
cam[0].second = -2e9;
while(cur<=q){
if(cam[cur].second==cam[cur-1].second){
vec.emplace_back(cur++);
continue;
}
check(vec);
vec.clear();
vec.emplace_back(cur++);
}
check(vec);
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%lf %lf",&lb[i].first,&lb[i].second);
scanf("%d",&m);
for(int i = 1; i <= m; i++) scanf("%lf %lf",&rb[i].first,&rb[i].second);
scanf("%d",&q);
for(int i = 1; i <= q; i ++) scanf("%lf %lf",&cam[i].first,&cam[i].second);
checkbod();
checkcam();
printf("%.6f\n",res);
return 0;
}\(B.The\ battle\ near\ the\ swamp\)
签到
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e4+7;
int n,m;
int main(){
scanf("%d %d",&n,&m);
int lft = 0, ene = 0;
for(int x,i = 1; i <= n; i++){
scanf("%d",&x);
if(x>m) lft+=x-m;
else ene+=m-x;
}
cout << lft << ' ' << ene << endl;
return 0;
}\(C.CVS\)
可持久化链表，可以用链式前向星
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 5e5+7;
struct CVS{
int tot;
CVS(){ tot = 1; }
struct NODE{
NODE *pre;
int ID;
NODE(int id = 0){
pre = nullptr;
ID = id;
}
};
struct Kamino{
NODE *ltail,*ttail;
Kamino(){
ltail = new NODE;
ttail = new NODE;
}
}kam[MAXN];
void learn(int ID, int p){
kam[ID].ttail = new NODE;
NODE* node = new NODE(p);
node->pre = kam[ID].ltail;
kam[ID].ltail = node;
}
void rollback(int ID){
NODE* node = new NODE(kam[ID].ltail->ID);
node->pre = kam[ID].ttail;
kam[ID].ttail = node;
kam[ID].ltail = kam[ID].ltail->pre;
}
void relearn(int ID){
NODE* node = new NODE(kam[ID].ttail->ID);
node->pre = kam[ID].ltail;
kam[ID].ltail = node;
kam[ID].ttail = kam[ID].ttail->pre;
}
void clone(int ID){
tot++;
kam[tot] = kam[ID];
}
int check(int ID){
return kam[ID].ltail->ID;
}
}CVS;
int n,m;
int read(){
int x = 0, f = 1;
char c = getchar();
while(c!='-'&&(c<'0'||c>'9')) c = getchar();
if(c=='-') f = -1,c = getchar();
while(c>='0'&&c<='9') x = x*10+c-'0', c = getchar();
return f*x;
}
int main(){
n = read(); m = read();
while(n--){
char op[20];
scanf("%s",op);
if(op[0]=='l'){ //learn
int id=read(),p=read();
CVS.learn(id,p);
}
else if(op[1]=='o'){ //rollback
int id=read();
CVS.rollback(id);
}
else if(op[1]=='e'){ //relearn
int id=read();
CVS.relearn(id);
}
else if(op[1]=='l'){ //clone
int id=read();
CVS.clone(id);
}
else if(op[1]=='h'){ //check
int id=read();
if(CVS.check(id)) printf("%d\n",CVS.check(id));
else printf("basic\n");
}
}
return 0;
}\(D.This\ cheeseburger\ you\ don't\ need\)
模拟
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int inf = 0x3f3f3f3f;
string S[5];
int main(){
IOS;
string s;
string ans="";
int tar=0;
for(int i=0;i<3;i++)S[i]="";
int f=0;
while(cin>>s){
int len=s.length();
if(s[0]=='(')tar=0,f++;
if(s[0]=='[')tar=1,f++;
if(s[0]=='{')tar=2,f++;
if(s[len-1]==')')f++;
if(s[len-1]==']')f++;
if(s[len-1]=='}')f++;
if(s[len-2]==']')f++;
if(s[len-2]=='}')f++;
if(s[len-2]==')')f++;
if(f==0){
ans+=s+' ';
continue;
}
if(s[0]!='('&&s[0]!='['&&s[0]!='{')S[tar]+=s[0];
if(s[len-1]==',')S[tar]+=s.substr(1,max(0,len-3));
else S[tar]+=s.substr(1,max(0,len-2));
if(s[len-1]==','){
if(len>=3&&s[len-2]!=')'&&s[len-2]!=']'&&s[len-2]!='}')S[tar]+=s[len-2];
S[tar]+=' ';
if(f==6){
ans+=S[2];
ans+=S[0];
ans+=S[1].substr(0,S[1].length()-1)+", ";
f=0;
for(int i=0;i<3;i++)S[i].clear();
}
continue;
}
if(s[len-1]!=')'&&s[len-1]!=']'&&s[len-1]!='}'&&len!=1)S[tar]+=s[len-1];
S[tar]+=' ';
if(f==6){
ans+=S[2];
ans+=S[0];
ans+=S[1];
f=0;
for(int i=0;i<3;i++)S[i].clear();
}
}
int len=ans.length();
for(int i=0;i<len-1;i++){
if(i==0&&ans[i]>='a'&&ans[i]<='z')cout<<char(ans[i]-32);
else if(i!=0 && ans[i]>='A'&&ans[i]<='Z')cout<<char(ans[i]+32);
else cout<<ans[i];
}
return 0;
}\(E.The\ Emperor's\ plan\)
组合数学 概率DP
\(f[x][y]\)表示当天晚上参议员中非spy的有\(x\)个，spy有\(y\)个的情况下，最终剩余非spy参议员的期望数量
边界条件是
1.\(x \le y\)这时非spy在晚上全被消灭，\(f[x][y]=0\)
2.\(y==0\) 这时全为非spy参议员，\(f[x][y]=x\)
然后依据题意进行\(dp\)，每次枚举白天被票出的人的个数进行转移，用\(ln\)和\(exp\)保证精度正确
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 222;
double ln[MAXN],f[MAXN][MAXN];
double lnC(int A, int B){ return ln[A]-ln[B]-ln[A-B]; }
double percentage(int a, int x, int b, int y){ return exp(lnC(x,a)+lnC(y,b)-lnC(x+y,a+b)); }
double solve(int x, int y){
if(f[x][y]!=-1) return f[x][y];
if(x<=y) return f[x][y] = 0;
if(y==0) return f[x][y] = x;
x-=y;
int tot = x+y;
double res = 0;
for(int k = 1; k < tot; k++){
double tp = 0;
for(int i = max(0,k-y); i <= min(x,k); i++) tp += solve(x-i,y-k+i)*percentage(i,x,k-i,y);
res = max(res,tp);
}
return f[x+y][y] = res;
}
int n,k;
int main(){
ln[0] = 0;
for(int i = 1; i < MAXN; i++) ln[i] = ln[i-1]+log(i);
for(int i = 0; i < MAXN; i++) for(int j = 0; j < MAXN; j++) f[i][j] = -1;
scanf("%d %d",&n,&k);
printf("%.6f\n",solve(n-k,k));
return 0;
}\(F.Illegal spices\)
题目保证答案存在，那就把前\(n-m\)个都设为\(1\)，后面的\(m\)个贪心地取就好了
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
int n,m,p;
vector<int> vec;
int main(){
scanf("%d %d %d",&n,&m,&p);
int_fast64_t sum = n - m;
int num = n - m, cur = 2;
for(int i = 1; i <= n-m; i++) vec.emplace_back(1);
for(int i = n-m+1; i <= n; i++){
if(num*100<p*(i-1)){
cur++;
num = i - 1;
}
sum+=cur;
vec.emplace_back(cur);
}
cout << sum << endl;
for(int x : vec) cout << x << ' ';
return 0;
}\(G.Cipher\ Message\ 3\)
KMP+FFT 不会
\(H.Those\ are\ not\ the\ droids\ you're\ looking\ for\)
出入的时间分开跑二分图匹配即可，如果能完全匹配则说明没有说谎
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1111;
int a,b,n,match[MAXN];
bool vis[MAXN];
vector<int> G[MAXN];
pair<int,int> sta[MAXN];
bool dfs(int u){
vis[u] = true;
for(int v : G[u]){
if(match[v]==-1||(!vis[match[v]]&&dfs(match[v]))){
match[v] = u;
return true;
}
}
return false;
}
int go(){
memset(match,255,sizeof(match));
int tot = 0;
for(int i = 1; i <= n; i++){
if(sta[i].second==0){
memset(vis,0,sizeof(vis));
if(dfs(i)) tot++;
else return tot;
}
}
return tot;
}
int main(){
scanf("%d %d %d",&a,&b,&n);
for(int i = 1; i <= n; i++) scanf("%d %d",&sta[i].first,&sta[i].second);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){
if(sta[i].second==0&&sta[j].second==1&&(sta[j].first-sta[i].first>=a||(sta[j].first-sta[i].first<=b&&sta[j].first-sta[i].first>0))){
G[i].emplace_back(j);
}
}
if(go()*2==n){
printf("No reason\n");
for(int i = 1; i <= n; i++) if(sta[i].second==1){
printf("%d %d\n",sta[match[i]].first,sta[i].first);
}
}
else printf("Liar\n");
return 0;
}\(I.The\ old\ Padawan\)
先双指针将每个点会回到的点找出来，然后暴力就行了
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using LL = int_fast64_t;
const int MAXN = 1e5+7;
int n,m,cur;
LL k,A[MAXN],tk[MAXN],res,pos[MAXN];
int main(){
scanf("%d %d %I64d",&n,&m,&k);
for(int i = 1; i <= n; i++) scanf("%I64d",&A[i]);
int l = 0,r = 1;
LL sum = A[1];
while(r<=n){
while(sum-A[l+1]>k) sum-=A[++l];
pos[r] = l;
sum+=A[++r];
}
for(int i = 1; i <= m; i++) scanf("%I64d",&tk[i]);
for(int i = 1; i <= m; i++){
if(n-cur<tk[i]-res) break;
int dur = tk[i] - res - 1;
res += dur+1;
cur += dur;
cur = pos[cur];
}
if(cur<n) res+=n-cur;
cout << res << endl;
return 0;
}\(J.The\ secret\ module\)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章