注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[SRM660]  

2015-06-05 11:37:45|  分类: 比赛 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
开心爆0了...原因是第一题second打成first

250:
题意:
给你一个矩阵d,和两个偏移数组x[],y[]
如果你选择一个station:(a,b)那么它可以控制的点是所有{(a+x[k],y+y[k]) | k<x.size(),且该点合法}
请选择两个station使得控制的总点集的权值和最大
矩阵 <= 100*100
x.size()=y.size() < 10
题解:
求出所有station的收益
首先枚举第一个station,然后从大到小枚举排好序的station,如果这个station被前面的影响了,就消除影响更新答案,
否则更新答案后结束枚举

500:
题意:
邀请n个人聚会,每个人可能有至多一个讨厌的人。
邀请顺序是一个1~n的排列,一个人答应邀请当且仅当他讨厌的人没有参加(还没有邀请或没有答应邀请)
求期望参加人数
n<=1e6(原题是n<=50)
题解:
ANS = ∑第i个人参加的概率
设dp[i] = ∑-(-1)^i/(i!)
对于从i出发一条长为L的链,概率就是dp[L]
由于环的情况下最后一条边是不对答案造成影响的,所以当成链看就好了
dp[i]的原因:
dp[1] 显然 =1 
dp[2] 中导致不能选1的是2,1 ,概率是dp[1] - 1/(2!)
dp[3] 中加入了3的影响,显然如果3对1有影响必须是3->2->1这样的情况,所以概率是dp[2] + 1/(3!)
依次类推得到dp[n]

250:

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 100+10;
short map[N][N],map2[N*N];
int n,m,kn;
typedef pair<int,int> Data;
vector<int>pos[N*N],go[N*N];
Data data[N*N];
int dn,v[N*N],dval[N*N],ans[N*N];
bool cmp(const Data&a,const Data&b){return a > b;}
class Coversta{
int calc(int x,int y){return (x-1)*m + y;}
public:
int place(vector <string> MAP, vector <int> xi, vector <int> yi){
int i,j,k,a,b,re=0;
n = MAP.size();m = MAP[0].size();kn = xi.size();
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
a = calc(i,j);
map2[a] = map[i][j] = MAP[i-1][j-1]-'0';
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
int tmp=0,x,y;
a = calc(i,j);
for(k=0;k<kn;k++){
x = i + xi[k];
y = j + yi[k];
if(!(1<=x && x<=n && 1<=y && y<=m))continue;
tmp += map[x][y];
b = calc(x,y);
pos[b].push_back(a);
go[a].push_back(b);
}
re = max(re,tmp);
data[++dn] = Data(tmp,a);
ans[a] = tmp;
}
sort(data+1,data+1+dn,cmp);
int nn = n*m;
for(i=1;i<=nn;i++){
int tmp = ans[i];
for(j=0;j<go[i].size();j++){
b = go[i][j];
for(k=0;k<pos[b].size();k++){
a = pos[b][k];
if(v[a] != i)v[a] = i,dval[a] = 0;
dval[a] += map2[b];
}
}
for(j=1;j<=dn;j++)
if(data[j].second!=i){
if(v[data[j].second] == i){
re = max(tmp + data[j].first - dval[data[j].second],re);
if(re == 47)
re = 47;
}else{
re = max(tmp + data[j].first,re);
if(re == 47)
re = 47;
break;
}
}
}
return re;
}
}fuck;
vector<string> ins =

{"34113",
"87427",
"79319",
"86502"}
;
vector<int>inx=
{3, 0, 0, 2, -1, 3, -3, 3, -1}
,iny=
{0, 0, 1, 1, 3, -1, -1, -4, -4}
;
int main(){
int i,j;
j = fuck.place(ins,inx,iny);
printf("%d\n",j);
return 0;
}


500:

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long double ld;
const int N = 1e6+10;
int n,m,du[N],list[N];
ld dp[N];
int v[N],len[N],dep[N];
queue<int>dui;
class Privateparty{
void dfs(int i,const vector<int> &d){
v[0]++;list[0]=0;
int now = i;
while(1){
len[v[0]]++;
v[now] = v[0];
list[++list[0]] = now;
if(v[d[now-1]+1])break;
now = d[now-1]+1;
}
for(int i=1;i<=list[0];i++)
dep[list[i]] = len[v[0]];
}
void dfs2(int now,const vector<int >&d){
if(dep[now])return;
list[0]=0;
while(1){
list[++list[0]] = now;
if(dep[d[now-1]+1]){
dep[now] = dep[d[now-1]+1] + 1;
break;
}
now = d[now-1]+1;
}
for(int i=list[0]-1;i;i--)
dep[list[i]] = dep[list[i+1]] + 1;
}
public:
double getexp(vector<int> d){
int i,j;
ld re=0;
n = d.size();
for(i=1;i<=n;i++){
du[d[i-1]+1]++;
}
for(i=1;i<=n;i++)
if(!du[i]){
dui.push(i);
}
while(!dui.empty()){
int now = dui.front();dui.pop();
v[now] = -1;
if(!(--du[d[now-1]+1])){
dui.push(d[now-1]+1);
}
}
ld tmp=1;
for(i=1;i<=n;i++){
dp[i] = dp[i-1] + tmp;
tmp *= -1./(i+1);
}
for(i=1;i<=n;i++)
if(!v[i]){
dfs(i,d);
}
for(i=1;i<=n;i++){
dfs2(i,d);
//printf("%d ",dep[i]);
re += dp[dep[i]];
}
return re;
}
}fuck;
vector<int> ina=
{28, 21, 4, 11, 7, 22, 23, 17, 25, 26, 24, 26, 6, 2, 10, 21, 7, 27, 21, 12, 18, 27, 8, 4, 2, 1, 7, 13, 1, 29}
;
int main(){
int i,j;
double re;
re = fuck.getexp(ina);
printf("\n%.2f\n",re);
return 0;
}


  评论这张
 
阅读(0)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017