Moscow Subregional 2013.

比赛连接

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006570

总叙

一个铜牌队的题解

剩下的题,大概很久以后才会补了,太累了。。。。

A

队友做的,我吃瓜群众不知道

#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std; const int maxn = 1e4 + 15;
int K[maxn]; int main(int argc,char *argv[]){
int N=read();
rep(i,1,N) K[i]=read();
if( N < 3 ) pf("0\n");
else{
sort( K + 1 , K + N + 1 );
int mx = K[N] ;
long long sum = 0;
for(int i = 1 ; i < N ; ++ i) sum += K[i];
if( mx > 2LL * sum ) cout << sum << endl;
else cout << (1LL*mx + sum) / 3LL << endl;
}
return 0;
}

B

队友做的,吃瓜群众还是不知道

#include <bits/stdc++.h>
#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define pb push_back
#define mp make_pair
#define sf scanf
#define pf printf
#define two(x) (1<<(x))
#define clr(x,y) memset((x),(y),sizeof((x)))
#define dbg(x) cout << #x << "=" << x << endl;
const int mod = 1e9 + 7;
int mul(int x,int y){return 1LL*x*y%mod;}
int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
using namespace std; const int maxn = 20 + 15;
char str[maxn];
int len,vis[maxn][1<<16][2];
string dp[maxn][1<<16][2];
char number[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int use[20]; inline void up(string & x , string v){
if( x == "" ) x = v;
else x = min( x , v );
} int main(int argc,char *argv[]){
//freopen("in.txt","r",stdin);
sf("%s",str+1);
len = strlen( str + 1 );
vis[0][0][0] = 1;
rep(i,0,len-1) rep(mask,0,two(16)-1) rep(f,0,1) if(vis[i][mask][f]){
int st = str[i + 1] <= '9' ? str[i + 1]-'0' : str[i + 1] - 'A' + 10;
if( f ) st = 0;
rep(add , st , 15 )
if( ( mask >> add & 1 ) == 0 ){
up( dp[i + 1][ mask | two( add ) ][ f | ( add > st ) ] , dp[i][mask][f] + number[add] );
vis[i + 1][mask | two( add )][ f | (add > st) ] = 1;
}
}
string ans = "GGGGGGGGGGGGGGGGGGGGGGGGGGG";
rep(mask,0,two(16)-1) if(vis[len][mask][1]) ans=min(ans,dp[len][mask][1]);
if( ans == "GGGGGGGGGGGGGGGGGGGGGGGGGGG" ){
rep(i,1,len+1){
int st = i == 1 ? 1 : 0;
rep(j,st,15){
if(!use[j]){
if( j <= 9 ) cout << j;
else cout << (j - 10) + 'A';
use[j] = 1;
break;
}
}
}
cout << endl;
}else cout << ans << endl;
return 0;
}

F

题意:有一个地方有两种交通工具,地下的需要28元,地上的需要26元,他可以花44元使得这90分钟随便坐车。

让你输出这个人如果贪心的去坐车,和最优策略去坐车的花费是多少。

题解:数据范围1500,所以DP就好了,这道题读题比做题难。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1500;
int n;
int t[maxn],op[maxn];
int s[3];
long long dp[maxn];
int main(){
s[1]=28;
s[2]=26;
scanf("%d",&n);
for(int i=1;i<=n;i++){
string s1,s2;
cin>>s1>>s2;
int now = 0;
for(int j=0;j<2;j++)
now = now*10 + s1[j]-'0';
int next = 0;
for(int j=3;j<s1.size();j++)
next = next*10 + s1[j]-'0';
t[i]=now*60+next;
if(s2[0]=='U')op[i]=1;
else op[i]=2;
}
t[n+1]=100000000;
long long ans1 = 0;
for(int i=1;i<=n;i++){
long long tmp = 0;
int flag = 0;
int j=i;
for(;j<=n;j++){
tmp+=s[op[j]];
if(op[j]==1)flag=1;
if(t[j+1]-t[i]>90)break;
if(op[j+1]==1&&flag)break;
}
if(tmp<44)ans1+=tmp;
else ans1+=44,i=j;
}
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]+s[op[i]];
int flag = 0;
if(op[i]==1)flag=1;
for(int j=i-1;j>=1;j--){
if(flag&&op[j]==1)break;
if(op[j]==1)flag=1;
if(t[i]-t[j]>90)break;
dp[i]=min(dp[i],dp[j-1]+44);
}
//cout<<dp[i]<<endl;
}
cout<<ans1<<" "<<dp[n]<<endl;
}

H

这场比赛的签到水题

#include<bits/stdc++.h>
using namespace std; int main(){
int x1,y1,x2,y2,x3,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
if(x1<=x3&&x3<=x2&&y1<=y3&&y3<=y2)puts("Yes");
else puts("No");
}

I

题意:有n个集合,然后给你两两集合共有的元素,问你能不能构造出来这些集合,数据范围200

题解:直观的想法就是共有的就直接插进去,然后最后check一下就好了。我感觉直接暴力是n^4的,所以我bitset了一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
int v1[maxn*maxn],v2[maxn*maxn];
vector<int> v3[maxn*maxn];
bitset<10005>S[205];
bitset<10005>tmp;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n*(n-1)/2;i++){
scanf("%d%d",&v1[i],&v2[i]);
int num;scanf("%d",&num);
for(int j=1;j<=num;j++){
int x;scanf("%d",&x);
S[v1[i]][x]=1;
S[v2[i]][x]=1;
v3[i].push_back(x);
}
sort(v3[i].begin(),v3[i].end());
}
int flag = 0;
for(int i=1;i<=n*(n-1)/2;i++){
tmp = S[v1[i]]&S[v2[i]];
if(tmp.count()>v3[i].size()){
printf("No\n");
return 0;
}
}
printf("Yes\n");
for(int i=1;i<=n;i++){
printf("%d",S[i].count());
for(int j=0;j<10005;j++){
if(S[i][j])printf(" %d",j);
}
printf("\n");
}
}

K

题意:给你x[-1],x[0],A,B,C,然后X[i] = (AX[i-2] + BX[i] + C )%2^32

然后让你算出[1,n]的xi值之后,输出前k大的,n<=1e8,k<=2e5

题解:这种题一看就是瞎JB莽,我们队分情况讨论了很多种……

但是似乎直接前面暴力2e5个数,后面暴力2e5个,再for一遍就好了。。。

尴尬。

#include<bits/stdc++.h>
using namespace std;
const int mod = 0x7fffffff;
vector<int> pppp;
int x0,x1,A,B,C;
int get(){
int a = (A*x0+B*x1+C)&(mod);
return a;
}
int n,k;
struct Heap
{
const static int HeapSize = 2e5 + 500;
int val[HeapSize] , sz; //向上维护
void maintain_up(int pos){
int cur = pos , pre = cur >> 1;
while(pre){
if(val[cur] < val[pre]) swap(val[cur] , val[pre]) , cur = pre;
else break;
pre = cur >> 1;
}
} //向下维护
void maintain_down(int pos){
int cur = pos;
while(cur * 2 <= sz){
int lson = cur << 1;
int rson = cur << 1 | 1;
if(rson > sz) rson ^= 1;
int nxt = lson;
if(val[rson] < val[lson]) nxt = rson;
if(val[cur] > val[nxt]) swap(val[cur],val[nxt]) , cur = nxt;
else break;
}
}
void insert(int x){
val[++sz] = x;
maintain_up(sz);
} int top(){
return val[1];
} void pop(){
if(sz==0) return;
swap(val[1] , val[sz--]);
maintain_down( 1 );
} void init(){ sz = 0 ;}
}heap;
void solve1(){
heap.init();
int tmp = get();
x0=tmp,swap(x0,x1);
heap.insert(tmp);
int now = heap.top();
for(int i=2;i<=k;i++){
int tmp=get();
heap.insert(tmp);
now=heap.top();
x0=tmp,swap(x0,x1);
}
for(int i=k+1;i<=n;i++){
int tmp = get();
if(now<tmp){
heap.pop();
heap.insert(tmp);
now=heap.top();
}
x0=tmp,swap(x0,x1);
}
vector<int> ans;
for(int i=1;i<=k;i++){
ans.push_back(heap.top());
heap.pop();
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf("%d ",ans[i]);
printf("\n");
}
void solve2(){
for(int i=1;i<=k;i++)
printf("%d ",C);
printf("\n");
}
int get1(int x){
return (x1+C*x)&(mod);
}
void solve3(){
heap.init();
int num = min(200000,n);
for(int i=1;i<=min(200000,n);i++)
pppp.push_back(i);
for(int i=n;i>=max(1,n-200000);i--)
pppp.push_back(i);
sort(pppp.begin(),pppp.end());
pppp.erase(unique(pppp.begin(),pppp.end()),pppp.end());
int tmp = get1(pppp[0]);
heap.insert(tmp);
int now = heap.top();
for(int i=1;i<pppp.size();i++){
int tmp=get1(pppp[i]);
if( heap.sz < k ){
heap.insert( tmp );
now = heap.top();
}else if(now<tmp){
heap.pop();
heap.insert(tmp);
now=heap.top();
}
}
int j = 0;
reverse(pppp.begin(),pppp.end());
for(int i=n;i>=1;--i){
while(j<pppp.size()&&pppp[j]>i) ++ j;
if( j < pppp.size() && pppp[j] == i) continue;
int tmp = get1(i);
if( heap.sz < k ){
heap.insert( tmp );
now = heap.top();
}
else if(now<tmp){
heap.pop();
heap.insert(tmp);
now=heap.top();
}
}
vector<int> ans;
for(int i=1;i<=k;i++){
ans.push_back(heap.top());
heap.pop();
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf("%d ",ans[i]);
printf("\n");
}
int get2(int x){
if(x&1)return (x0+(x+1)/2*C)&(mod);
else return (x1+x/2*C)&(mod);
//return (x0+C*x)&(mod);
}
void solve4(){
heap.init(); int num = min(200000,n);
for(int i=1;i<=min(200000,n);i++)
pppp.push_back(i);
for(int i=n;i>=max(1,n-200000);i--)
pppp.push_back(i);
sort(pppp.begin(),pppp.end());
pppp.erase(unique(pppp.begin(),pppp.end()),pppp.end()); int tmp = get2(pppp[0]);
heap.insert(tmp);
int now = heap.top(); for(int i=1;i<pppp.size();i++){
int tmp=get2(pppp[i]);
if( heap.sz < k ){
heap.insert( tmp );
now = heap.top();
}else if(now<tmp){
heap.pop();
heap.insert(tmp);
now=heap.top();
}
}
int j = 0;
reverse(pppp.begin(),pppp.end());
for(int i=n;i>=1;--i){
while(j<pppp.size()&&pppp[j]>i) ++ j;
if( j < pppp.size() && pppp[j] == i) continue;
int tmp = get2(i);
if( heap.sz < k ){
heap.insert( tmp );
now = heap.top();
}
else if(now<tmp){
heap.pop();
heap.insert(tmp);
now=heap.top();
}
}
vector<int> ans;
for(int i=1;i<=k;i++){
ans.push_back(heap.top());
heap.pop();
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
printf("%d ",ans[i]);
printf("\n");
}
int main(){
//freopen("a+b.in","r",stdin);
// freopen("out.txt","w",stdout);
srand(time(NULL));
scanf("%d%d",&n,&k);
cin>>x0>>x1>>A>>B>>C;
if(A==0&&B==0)solve2();
else if(A==0&&B==1)solve3();
else if(A==1&&B==0)solve4();
else if(A>=1||B>=1)solve1(); return 0;
}

最新文章

  1. js实现css3的过渡,需要注意的一点(浏览器优化)
  2. Sqoop2搭建及使用
  3. .Net深复制、浅复制
  4. HTTP压缩
  5. AngularJS 学习之路(1)
  6. Delphi 文件类型
  7. JS算法总结
  8. log4j使用教程详解(怎么使用log4j2)
  9. (step4.3.5)hdu 1501(Zipper——DFS)
  10. 关于C#泛型列表List&lt;T&gt;的基本用法总结
  11. [译]Java设计模式之解释器
  12. Windows环境下使用VS2005编译OpenSSL
  13. 安装spring tool suite时遇到的问题
  14. 使用spring框架,用xml方式进行bean装配出现“The fully qualified name of the bean&#39;s class, except if it serves...”
  15. R语言-默认镜像设置
  16. JDBC使用MYSQL的LOAD DATA LOACAL INFILE和LOAD DATA INFILE
  17. 用户人品预测大赛--就是gan队--竞赛分享
  18. ios 错误纪录
  19. having只用来在group by之后,having不可单独用,必须和group by用。having只能对group by的结果进行操作
  20. Jquery为动态添加的未来元素绑定事件

热门文章

  1. vux 获取后台数据
  2. [http session]
  3. Atitit。如何实现dip, di ,ioc ,Service Locator的区别于联系
  4. POJ 3984 迷宫问题(BFS)
  5. From MSI to WiX, Part 8 - Major Upgrade, by Alex Shevchuk
  6. spring+hibernate中的Result object returned from HibernateCallback isn&#39;t a List
  7. kettle工具实现报表导出的初步搭建
  8. JavaScript之数组五大迭代方法总结
  9. geotools实现多边形的合并&amp;缓冲区
  10. hadoop2.6.0实践:A01 问题处理 DEPRECATED: Use of this script to execute hdfs command is deprecated.
  11. syncer.go
  12. python中关于变量名失效的案例
  13. alfred3配置
  14. docker zabbix
  15. Django眼中的MVC
  16. JS event loop
  17. hdu3377
  18. HSSFWorkBooK用法 —Excel表的导出和设置
  19. c++ json 详解
  20. Picasso:开启大前端的未来