概述
Codeforces Round #288 (Div. 2) C
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
using namespace std;
/*
这题 题意没有理解得很对；
他的意思是： 每根蜡烛可以燃烧t秒 比如
一根蜡烛可以燃烧两s，且在t=1 时点燃；
1-2-3-4
就会燃烧1-2 2-3 ，第三秒是没有蜡烛燃烧的。
7 2 2
1 2 3 4 6 7 9
ANS=10
然后告诉你每个鬼魂到来的时间，要保证每个鬼混来的时候都至少有r根蜡烛燃烧
求总过程最少耗费的蜡烛
*/
int down[605],w[305];
map<int,int>up;
int main(){
//freopen("1.txt","r",stdin);
int m,t,r;
scanf("%d %d %d",&m,&t,&r);
for(int i=1;i<=m;i++){
scanf("%d",&w[i]);
up[w[i]]=-1;
}
int cnt=0;
for(int i=1;i<=600;i++){
cnt+=down[i];
// printf("cnt=%d %d - %dn",cnt,i,down[i]);
if(up[i]==-1){
if(cnt>=r)
continue;
int temp=r-cnt;
int pos=i;
// printf("pos=%d temp=%d n",pos,temp);
while(temp){
while(i-pos<=t && up[pos]==1){
pos--;
}
if(up[pos]!=1){
up[pos]=1;
down[pos+t]=-1; //熄灭的那一秒 就没了，1 + 2 =3 第二秒末就熄灭了
// printf("%d +t=%dn",pos,pos+t);
temp--;
if(pos+t<=i){
printf("-1n");
return 0;
// temp++; 必不可能完成了
}
}
else{
printf("-1n");
return 0;
}
}
cnt=r;
}
// cnt+=down[i]; 写在这里 前面continue 还怎么运行到这一步？
}
cnt=0;
for(int i=-600;i<=600;i++)
if(up[i]==1){
cnt++;
}
printf("%dn",cnt);
}反思： 对于这种题意存疑的题目，读题一定要稳，否则很容易找不到错，就会很伤。
Codeforces Round #373 (Div. 2)C
题意：给一个小数，以及一个数 n
问： 在四舍五入次数<=n次的情况下，能够得到的最大的数是多少：
注意只能够 四舍五入小数
6 1
10.245 = 10.25
6 2
10.245 = 10.3
wa:
7 1000000000
239.923
反思：这种题目，往往明了简单，但处理起来 颇为棘手，最恐怖的地方是wa,
然后在思维模式限定在一种情况的时候无法找到自己的错误，然后会卡题，会非常之难受
比如：wa 的一次就忘记输出24 之后的那个0
一定要耐心看自己的代码，或者多出几组数据去测试测试，别急着交题
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
using namespace std;
char str[200005];
int main(){
// freopen("1.txt","r",stdin);
int n,t;
scanf("%d %d",&n,&t);
scanf("%s",str+1);
int pos;
for(int i=1;i<=n;i++){
if(str[i]=='.'){
pos=i;
break;
}
}
int end=n;
for(int i=pos+1;i<=end;i++){
if(str[i]>='5' && t>0){
str[i]='0';
t--;
end=--i;
while(str[i]=='9' && i>pos){
i--;
}
if(i==pos){
end=pos;
break;
}
else{
str[i]++;
i-=2;
}
}
}
if(end==pos){
int i=pos-1;
while(str[i]=='9' && i>0){
i--;
}
if(i==0){
printf("1");
for(int j=0;j<pos-1;j++)
printf("0");
printf("n");
}
else{
str[i]++;
for(int j=1;j<=i;j++)
printf("%c",str[j]);
for(int j=i+1;j<pos;j++) //不能忘记 后面还有0的啊
printf("0");
printf("n");
}
}
else{
for(int i=1;i<=end;i++)
printf("%c",str[i]);
printf("n");
}
}Codeforces Round #333 (Div. 2) C. The Two Routes
题意： 有一辆火车和一辆公交车，分别只能走铁路和公路。
给你一个图 n个点,m条边 ，无向边，无重边
给的边全是铁路， 若是两点之间无边，则认为他们之间有一条公路
两辆车不能同时在一个城市里面，行驶的花费都是1
问：两辆车都从1 到 n 需要花费的最小的时间是多少？
如果某辆车无法到达输出-1
分析：如果1-n没有铁路，那么必然有公路
所以肯定有一辆车 是可以直接到达的，如果是火车可直接到达，那么接下来我们dfs公交车即可，所有已经建好的边都不可以走，其他都可以走
反之亦然。
复习下dij的最短路。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
using namespace std;
int mp[405][405];
void add(int u,int v){
mp[u][v]=mp[v][u]=1;
}
typedef pair<int, int> P;
int dis[405][405];
int flag[405];
int n,m;
void dijkstra(int s,int cnt)
{
memset(flag,0,sizeof(flag));
priority_queue<P, vector<P>, greater<P> > que;
memset(dis[s], -1, sizeof(dis[s]));
dis[s][s] = 0; //到本身为0；
que.push(P(0, s));
while (!que.empty())
{
P p = que.top(); que.pop();
int v = p.second;
if (flag[v]) continue; //做过就跳过
flag[v]=1;
for (int i = 1;i <= n; ++i)
{
if(mp[v][i]==cnt)
continue;
// printf("%d ->%d ans=%dn",v,i,dis[1][n]);
if (dis[s][i] > dis[s][v] + 1 || dis[s][i]==-1)
{
dis[s][i] = dis[s][v] + 1;
que.push(P(dis[s][i], i));
}
}
}
}
int main(){
//freopen("1.txt","r",stdin);
scanf("%d %d",&n,&m);
int temp=0;
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
if(u==1 && v==n)
temp=1;
if(v==1 && u==n)
temp=1;
add(u,v);
}
dijkstra(1,temp);
if(dis[1][n]==-1){
printf("-1n");
}
else
printf("%dn",dis[1][n]);
}Codeforces Round #330 (Div. 2) B、C
C. Warrior and Archer
这是一个很有意思的题目，想到了 非常之简单，没想到的话又会觉得很难。
题意：
给n 个位置：N<2000000 且n必定为偶数
位置大小在 0-1e9 之间
然后两个人开始博弈： 一个是弓箭手，一个是战士。 两个人轮流操作，战士先开始 操作。
每个操作： ban掉一个位置，相当于删掉它
…..
一直操作下去，知道只有两个位置了， 这两个位置之间的距离就是最终距离。
战士希望最终距离越近越好，弓箭手希望最近距离越远越好。 假设两个人都足够聪明，问最终距离是多少？
分析：
删除的位置一共就n-2个， 最后只剩下 两个位置
那么在原来的序列中
1.2.3.4.5.6.7.8…
……l…………..r…
如果战士想要缩小这个l，r 那么他就必须 [l,r]外面的数全部都删除掉的情况下，[l,r]里面的数还必须有所保留。。然后删除r
同理 弓箭手反之
问题来了 如果最后保留的这个两个位置 [l,r]
那么 里面的数 == 外面的数 这个是不是必然成立呢？ 这是肯定的，因为战士不回去删外面的点，弓箭手也不会去删里面的点。
所以我们只要对序列中的 区间 逐个取值，那么是取最大值还是最小值？
想想：
1 2 3 4 5 6 7 8 9 10 11 12
. .
战士先手操作，如果[4,10]这个区间 是最小的，那战士直接ban掉11 就确定了这个区间，如果弓箭手去破坏4， 战士依次把 12 、1、2、3破坏，那剩下的区间肯定比[4,10]还小
因为是战士先手，所以战士决定了取最小值，如果是弓箭手先手，那就肯定是取最大值了。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
using namespace std;
/*
仔细想想 n是一个偶数：
所以 每个人ban掉了 (n-2)/2 个点
我们假设最后形成的区间是[l,r] .现在我们假设区间内外的点 点数是相等的。
那你觉得战士会 ban [l,r]里面的任何一个点吗？
如果他ban里面的点，那么外面的点（...<l ,r<...） 就 会比里面的点多，那么弓箭手就必然会把里面的点全删掉
到时候这个区间 就会扩大！
所以在区间内外点相等的情况下，战士必不可能删掉区间里面的点。
同理弓箭手也比不可能去删区间外面的点
我们 以 （n-2）/2 为长度，去删选出一个距离最小的区间即可 ： 因为这两个人都很聪明！！！
1*/
int pos[200005];
int main(){
//freopen("1.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&pos[i]);
sort(pos+1,pos+n+1);
int len=(n-2)/2;
ll ans=pos[1+len+1]-pos[1];
for(int i=2;i+len+1<=n;i++){
ll temp=pos[i+len+1]-pos[i];
ans=min(ans,temp);
}
printf("%I64dn",ans);
}Educational Codeforces Round 5 c. The Labyrinth
题意： 给一个n*m的矩阵，矩阵包括 ‘.’ 和 *
问 对每个* 询问如果把这个*变成点，将会形成的连通块的数量：
input
3 3
*.*
.*.
*.*
output
3.3
.5.
3.3
input
4 5
**..*
..***
.*.*.
*.*.*
output
46..3
..732
.6.4.
5.4.3嗨呀，当时使用并查集做的，只是感觉写起来颇为麻烦。
而且我写的真的是太丑了。。。 后面想了想其实其实没必要并查集呢，写个bfs，将连通块的fa都定义一下 会简单很多，后面记得还有一道题 我是这样做的。。。
反思： 这种题很容易写得麻烦，写之前一定要去想清楚再动手敲，否则就是霸占着机子大量时间，很容易导致血崩的。
如果想清楚了，不要急，心态要稳，一步一步敲，稳着敲会好很多。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
char mp[1005][1005];
int fa[1005*1005];
int num[1005*1005];
int find(int x) {
if (fa[x] != x)
return fa[x]=find(fa[x]);
return fa[x];
}
void together(int x, int y) {
fa[x] = find(x);
fa[y] = find(y);
if (fa[x] != fa[y]) {
num[fa[x]] += num[fa[fa[y]]];
fa[fa[y]] = fa[x]; // 将y 并入x 集合之中
}
}
int ans[1005][1005];
int main() {
//freopen("1.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for (int j = 1; j <= m; j++) {
fa[(i - 1) * m + j] = (i - 1) * m + j;
num[(i - 1) * m + j]++;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '*')
continue;
int l = 0, r = 0, u = 0, d = 0;
int pos = (i - 1) * m + j;
if (j != 1)
l = pos - 1;
if (j != m)
r = pos + 1;
if (i != 1)
u = pos - m;
if (i != n)
d = pos + m;
// printf("pos=%d n",pos);
// printf("%c %c %c %cn",mp[i][j - 1],mp[i][j +1],mp[i+1][j],mp[i-1][j ]);
if (0 < l && l <= m * n) {
if (mp[i][j - 1] == '.') {
together(l, pos);
// continue;
}
}
if (0 < r && r <= m * n) {
if (mp[i][j + 1] == '.'){
together(r, pos);
// continue;
}
}
if (0 < u && u <= m * n) {
if (mp[i - 1][j] == '.'){
together(u, pos);
// continue;
}
}
if (0 < d && d <= m * n) {
if (mp[i + 1][j] == '.'){
together(d, pos);
// continue;
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '.') {
ans[i][j] = '.';
continue;
}
int l = 0, r = 0, u = 0, d = 0;
int pos = (i - 1) * m + j;
if (j != 1)
l = pos - 1;
if (j != m)
r = pos + 1;
if (i != 1)
u = pos - m;
if (i != n)
d = pos + m;
// printf("pos=%d n",pos);
// printf("%d %d %d %d n",l,r,u,d);
int a = 0, b = 0, c = 0, x = 0;
if (0 < l && l <= m * n) {
if (mp[i][j - 1] == '.') {
a += num[find(l)];
}
}
if (0 < r && r <= m * n) {
if (mp[i][j + 1] == '.')
b += num[find(r)];
}
if (0 < u && u <= m * n) {
if (mp[i - 1][j] == '.')
c += num[find(u)];
}
if (0 < d && d <= m * n) {
if (mp[i + 1][j] == '.')
x += num[find(d)];
}
int fa1=0,fa2=0,fa3=0,fa4=0;
if(l) fa1=fa[l];
if(r) fa2=fa[r];
if(u) fa3=fa[u];
if(d) fa4=fa[d];
int cnt = a ;
if(fa2!=fa1)
cnt+=b;
if(fa3!=fa1 && fa3!=fa2)
cnt+=c;
if(fa4!=fa3 && fa4!=fa2 && fa4!=fa1)
cnt+=x;
cnt++;
cnt%=10;
// printf("%d %d %d %d =%dn",a,b,c,x,cnt);
ans[i][j] = cnt;
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if(ans[i][j]=='.'){
printf(".");
}
else
printf("%d",ans[i][j]);
}
printf("n");
}
return 0;
}hdu 5073
题意：
给你n个数，代表n个球的位置，移动k个球，使得Σwi*di^2 最小
wi 是行星质量相当于1，di 是行星距离质心的距离，质心=（pos1+pos2…+posn）/n.
n(1 ≤ n ≤ 50000) and k(0 ≤ k ≤ n)
也就是说可以移动k个球 放到n-k个球的区间里面，求最小值
Sample Input
2
3 2
-1 0 1
4 2
-2 -1 1 2
Sample Output
0
0.5
思路：一开始很naive ，想着 取区间长度 为 n-k ，然后算一遍方差。 其实这个xjb搞的方法根本证明不了其正确性。
如果每一个 区间长度 为 n-k 的区间都算一遍方差，就是 n*n 的复杂度了。
碰到这种数学公式的情况下咋办呢？ 切记：尝试着 把这个式子推导推导
方差的公式：
Σ(a[i]-ave)^2 /n
Σa[i]^2 + Σave^2 - Σ2* ave* a[i] /n
这就降到On 了
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
double a[50005];
int sum1[50005];
ll sum2[50005];
int main() {
//freopen("1.txt", "r", stdin);
int t;
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d %d",&n,&k);
int len=n-k;
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]); // ，用int 存可能爆int？
}
sort(a+1,a+n+1);
sum1[0]=sum2[0]=0;
sum1[1]=a[1];
sum2[1]=a[1]*a[1];
for(int i=2;i<=n;i++){
sum1[i]=sum1[i-1]+a[i];
sum2[i]=sum2[i-1]+a[i]*a[i];
}
//l l+len-1
if(len==0||len==1){
printf("0.000000000000n");
continue;
}
double maxn;
for(int i=1;i + len-1<=n;i++){
double temp;
double I;
I=double(sum1[i+len-1]-sum1[i-1])/len*1.0;
temp=sum2[i+len-1]-sum2[i-1] + I*I*len -(double)2.0*I*(sum1[i+len-1]-sum1[i-1]);
if(i==1)
maxn=temp;
else
maxn=min(maxn,temp);
}
printf("%.12fn",maxn);
}
return 0;
}
cf 285 div2 :C. Misha and Forest
这个题，感觉是真的值得一做：
给一个n
然后下面n行 0~n-1
第i行： a b ； a表示序号为i的点的度数， b表示i周围连接的点的异或和。
然后要你构造出一个图，满足题目给出的条件；
比如：
input
3
2 3
1 0
1 0
output
2
1 0
2 0
分析：
嗨呀，xjb构造了半天，以后是个构造题，感觉图论的学到狗身上去了，一点图论的思维都不在了 ，
这种题必然是铜即其以下，这种题的做不出来，谈什么拿牌啊。。。
这种题，如果按构造的思维去搞的话，限制的东西太多了，无法构造。所以我们只能抓住题目中的提示去弄， 比如所谓异或和，那么0^x=x； 那么那些叶子节点，是不是就满足0^x=x 呢？ 所以，叶子节点上的b，就必然是它所连之点。所以我们类似拓扑排序那样写个队列，一个一个弄出来就好了
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
int d[100000];
int s[100000];
/*
这题想不出来，真的很伤！
0^ x=x;
那么叶子节点呢？？？ 想到叶子节点都不会吗？？
如果你知道有叶子节点x，那么 s[x]=y; 那就意味这x-y ，然后我们吧y的度数-1，把y的异或和维护一下
一直做到没有叶子节点，类似拓扑排序就好。
*/
int main(){
int n;
cin>>n;
queue<int> que;
int sum=0;
for(int i=0;i<n;i++){
scanf("%d%d",&d[i],&s[i]);
if(d[i]==1)
que.push(i);
sum+=d[i];
}
cout<<sum/2<<endl;
while(!que.empty()){
int u=que.front();
que.pop();
if(d[u]==0)continue;
d[u]--; //
int v=s[u]; //
d[v]--; //
s[v]^=u; //
if(d[v]==1) que.push(v);
printf("%d %dn",u,v);
}
return 0;
}Codeforces Round #287 (Div. 2) C. Guess Your Way Out!
题意：
给你一颗标准的完全二叉树的高度
然后按照LRLRLRLRLR…的规则走
对于节点x，如果子节点l走过，那么跳过，继续走R，如果连续跳过两个节点L,R 我们返回x 的父亲结点。
然后告诉你 迷宫的出口在第 n 个叶子节点，问一共要走过多少个点，才能够走出迷宫。
错了大半天的dfs，强行弄出来了，看别人xjb循环一下就行了= =，我还是too young
思路也很简单：在dfs的过程中不断判断，迷宫 和即将走的节点 的关系，如果不在，就直接加上所有点，如果在继续找。
其实讲道理，自我感觉最近的dfs 长进不少。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
int flag=1; //先往左
ll h,n;
ll count(ll len){
if(len==1)
return 1;
ll ans=1;
ll l=0;
while(1){
if(ans*2<=len)
ans*=2,l++;
else
break;
}
// printf("?? l=%I64dn",l);
ll cnt=0;
for(int i=0;i<=l;i++){
cnt+=pow(2,i);
}
return cnt;
}
ll dfs(ll l,ll r,int flag){
// printf("%I64d %I64d %dn",l,r,flag);
if(l==r ){
return 1;
}
ll ans=1;
ll mid=(l+r)/2;
if(flag==1){
if(n<=mid){
ans+=dfs(l,mid,2);
}
else{
ans+=count(mid-l+1);
ans+=dfs(mid+1,r,1);
}
}
else{ //会往右边扫
if(n>mid){
ans+=dfs(mid+1,r,1);
}
else{
ans+=count(r-mid); //这里是r-（mid+1）+1;
ans+=dfs(l,mid,2);
}
}
// printf("ans =%I64dn",ans);
return ans;
}
int main(){
// freopen("1.txt","r",stdin);
scanf("%I64d %I64d",&h,&n);
ll r=pow(2,h);
ll l=1;
printf("%I64dn",dfs(l,r,1)-1);
return 0;
}Codeforces Round #375 (Div. 2)
B. Text Document Analysis
这题想讲一讲，因为是个小模拟题
感觉自己在模拟题上面吃过很多亏，经常被HACK ，我也是醉了。（捂脸
题意：统计下括号外面最长的单词和括号里面的单词数量
37
Hello_Vasya(and_Petya)__bye(and_OK)
输出：
5 4
wa了一发：
14
Q(_)_u(_U)HG
Output
1 1
Answer
2 1
因为自己写的代码，包括自己的想法，其实很少有去特意的留心这种 处理的末尾问题，这个东西
包括这个的末尾 括号外最长单词长度又忘记更新，其实这种末尾处理一定要特别特别在意
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
char str[300];
int main(){
//freopen("1.txt","r",stdin);
int n;
scanf("%d",&n);
scanf("%s",str+1);
int flag=1;
int ans=0;
int temp=0;
for(int i=1;i<=n;i++){
if(str[i]!='_' && str[i]!='(' && str[i]!=')' ){
if(flag==1){
temp++;
}
else
continue;
}
if(str[i]=='('){
ans=max(ans,temp);
flag=0;
temp=0;
continue;
}
if(str[i]==')'){
flag=1;
temp=0;
continue;
}
if(str[i]=='_'){
ans=max(ans,temp);
temp=0;
continue;
}
}
ans=max(ans,temp);
int ans2=0;
for(int i=1;i<=n;i++)
if(str[i]=='('){
int cnt=0;
int len=0;
for(int j=i+1;;j++){
if(str[j]==')'){
if(len>0) ans2++;
break;
}
if(str[j]=='_'){
if(len>0) cnt++;
len=0;
}
else{
len++;
}
}
ans2+=cnt;
}
printf("%d %dn",ans,ans2);
return 0;
}C. Polycarp at the Radio
题意也是贼恶心，不知道是我英文水平太差，还是这个俄罗斯人不行。。。
说 有个主播 要播放n首歌，主播只喜欢前m首歌，然后给你一个歌单。。。主播可以改变任何歌的播放。。。
但是 需要满足一下几个条件：
1.要使 （播放次数最少的歌） 的播放次数最大
2.然后还需要在操作数量尽量少的情况下满足，改变一次就相当于一次操作。
比如有两首歌播放了1次 ，那就是2
比如1 1 2 2 2 3 3 那就是2 歌曲1和3 都播放了两次
思路： 其实，（播放次数最少的歌） 的数量 和 操作数都是固定的。
一共n首歌 ，m 首喜欢的，那平均 每首歌放 n/m次， ans肯定就是这个值
所以我们只要把 每首歌的播放次数都达到这个 ans值就行了。 这就是最小的操作数量，然后 我们每次操作 对 没有达到ans的歌曲进行操作就好了，这里还有一个比较坑的就是：对不喜欢的 歌不一定要换掉，比如
7 3
1 1 2 2 3 3 4841315
这个操作数就是0，因为没必要去换掉最后一个
所以把队列改成map之后，我整个人都舒服多了。
强行优先队列是最坑的
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
int a[2005];
map<int,int>flag;
int main(){
//freopen("1.txt","r",stdin);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
flag[a[i]]++;
// printf("%d :%dn",a[i],flag[a[i]]);
}
int ans=n/m; //ans 至少有这么多
queue<int>qqq;
queue<int>que;
int op=0;
for(int i=1;i<=m;i++){
if(flag[i]<ans){
op+=ans-flag[i];
que.push(i);
}
}
while(!que.empty()){
int v=que.front();
que.pop();
for(int i=1;i<=n;i++){
if(a[i]>m ){
a[i]=v;
flag[v]++;
if(flag[v]>=ans)
break;
}
}
if(flag[v]>=ans)
continue;
for (int i = 1; i <= n; i++)
if (flag[a[i]]>ans) {
flag[a[i]]--;
a[i] = v;
flag[v]++;
if (flag[v] >= ans)
break;
}
}
printf("%d %dn",ans,op);
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
cout<<endl;
return 0;
}D - Lakes in Berland
题意： 矩阵处理的问题，矩阵被海洋包围， *代表陆地，.代表水。
和海洋相连接的都是海洋， 只有被陆地包围着的水域才是淡水湖， 然后给一个k， 初识状态下有大于k个连通块，然后问你最小要把多少个. 变成 * 才能够使矩阵里面只有k个连通的 湖水。
input
5 4 1
****
*..*
****
**.*
..**
output
1
****
*..*
****
****
..**很简单的题，吧所有的连通块找出来，然后按包含点的数量排序，然后把最小点数的几个连通块删除掉即可。
总结：
这一次没有用并查集了，而是用了bfs去处理各个矩阵的fa，所以处理起来简单很多。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
int n,m,k;
int vis[55][55];
char mp[55][55];
int be[55*55];
void init(int x,int y){
// printf("%d %dn",x,y);
vis[x][y]=1;
int id=(x-1)*m+y;
be[id]=0;
if(!vis[x+1][y] && mp[x+1][y]=='.')
init(x+1,y);
if(!vis[x-1][y] && mp[x-1][y]=='.')
init(x-1,y);
if(!vis[x][y-1] && mp[x][y-1]=='.')
init(x,y-1);
if(!vis[x][y+1] && mp[x][y+1]=='.')
init(x,y+1);
}
void bfs(int x,int y,int id){
int cnt=(x-1)*m+y;
if(be[cnt]==0 || be[cnt]==-1)
return;
be[cnt]=id;
vis[x][y]=1;
if(!vis[x+1][y] && mp[x+1][y]=='.')
bfs(x+1,y,id);
if(!vis[x-1][y] && mp[x-1][y]=='.')
bfs(x-1,y,id);
if(!vis[x][y-1] && mp[x][y-1]=='.')
bfs(x,y-1,id);
if(!vis[x][y+1] && mp[x][y+1]=='.')
bfs(x,y+1,id);
}
int vvis[55*55];
int f[55*55];
int num[55*55];
bool cmp(int a,int b){
return num[a]<num[b];
}
int main() {
//freopen("1.txt", "r", stdin);
scanf("%d %d %d",&n,&m,&k);
memset(be,-1,sizeof(be));
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
for(int j=1;j<=m;j++)
be[(i-1)*m+j]=(i-1)*m+j;
}
//MD 智障init
for(int i=1;i<=n;i++){
if(mp[i][1]=='.'){
init(i,1);
}
if(mp[i][m]=='.'){
init(i,m);
}
}
for(int j=1;j<=m;j++){
if(mp[1][j]=='.'){
init(1,j);
}
if(mp[n][j]=='.'){
init(n,j);
}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(be[(i-1)*m+j]!=0 && be[(i-1)*m+j]!=-1 && mp[i][j]=='.'){
if(!vis[i][j]){
bfs(i,j,(i-1)*m+j);
// printf("bfs=%d %dn",i,j);
}
}
int len=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(be[(i-1)*m+j]!=0 && be[(i-1)*m+j]!=-1 && mp[i][j]=='.'){
int fa=be[(i-1)*m+j];
if(!vvis[fa]){
f[len++]=fa; //把祖先放进去
vvis[fa]=1;
}
num[fa]++;
// printf("fa%d =%dn",fa,num[fa]);
}
}
int ans=0;
sort(f,f+len,cmp);
for(int i=0;i<len-k;i++){
ans+=num[f[i]];
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++){
if(be[(x-1)*m+y]==f[i])
mp[x][y]='*';
}
}
printf("%dn",ans);
for(int i=1;i<=n;i++)
printf("%sn",mp[i]+1);
return 0;
}GYM Higher Institute for Applied Sciences and Technology Collegiate Programming Contest 2016
三星比赛，又是9T 没啥突破。。。
G. Repeat it
讲讲这道题吧，给你m，n ，然后将 n复制粘贴 m次，然后问这个数对1000000007 取余
input
3
4 31
8 1
123 123
output
31313131
11111111
388853804有点像 数位dp,推一推不难退出
4 abcd
得到abcd abcd abcd abcd
如果当前段数是偶数：
那么 = abcd abcd*100000000 +abcd abcd= abcd abcd(100000000+1)，然后继续对abcdabcd进行处理
如果当前段数是奇数：abcd abcd abcd abcd abcd
那么= abcd*1e16 + abcd abcd abcd abcd = 然后再处理 abcd abcd abcd abcd
那么我们容易用一个dfs 完成他，进的用快速幂 处理
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
const ll mod=1e9+7;
int L;
ll poww(ll len) {
ll temp=10;
ll ans=1;
while (len) {
if (len % 2 == 1) {
ans = (ans%mod*temp%mod)%mod;
}
len /= 2;
temp = (temp*temp)%mod;
}
return ans;
}
ll dfs(ll m,ll n){
ll ans=0;
if(m==1)
return n;
if(m%2==1){
ans+=(n * poww(L*(m-1)))%mod;// %mod
}
m/=2;
ans+= (poww(L*(m)) + 1 )%mod * dfs(m,n);
return ans%mod;
}
int main() {
// freopen("1.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
ll m,n;
scanf("%I64d %I64d",&m,&n);
ll cnt=n;
L=0;
while(cnt>0){
cnt/=10;
L++;
}
// printf("len=%dn",L);
if(n==0){
printf("0n");
continue;
}
printf("%I64dn",dfs(m,n));
}
return 0;
}Good Bye 2014
C. New Year Book Reading
有一个书架，要从书架上拿书，每本书有序号， 以及重量。
拿书的时候要把 要拿书 上面的书全部都搬出来，然后放进去，然后把要拿的书放在最上面
然后给你每本书的重量， 以及一个看书的顺序；
问： 如果摆放最初的书架，使得搬书的总重量最小。
input
3 5
1 2 3
1 3 2 3 1
output
12思路：如果在某个时刻 把 i 拿出来看，那么 i a b c d 后面的abcd肯定都要搬动i ，
i a b c d i a b c d 如果后面再出一个i，那么我们就把后面的i单独列出来算一下贡献值就好，必要的搬运重量就这些。
如果是 i a b a 第二个a 是 是不需要搬动 i 的，所以所有的书至多只能有一次贡献。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
const ll mod = 1e9 + 7;
int w[1005];
int r[1005];
int flag[505];
int main() {
// freopen("1.txt", "r", stdin);
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
scanf("%d",&r[i]);
int ans=0;
for(int i=1;i<=m;i++){
memset(flag,0,sizeof(flag));
for(int j=i+1;j<=m;j++){
if(r[j]==r[i]) break;
if(!flag[r[j]]){
ans+=w[r[i]];
flag[r[j]]=1;
}
}
// printf("w=%d %dn",w[r[i]],ans);
}
printf("%dn",ans);
return 0;
}D. New Year Santa Network
题意：给你一棵树，再给出一种操作，就是将树上的一条边的权值减小，每次操作后要输出一个期望，这个期望是从树上任取三点a，b，c，他们的距离和（d（a,b）+d(a,c)+d(b,c)）。
input
3
2 3 5
1 3 3
5
1 4
2 2
1 2
2 1
1 1
output
14.0000000000
12.0000000000
8.0000000000
6.0000000000
4.0000000000这个题有点意思，当时想了一会儿
首先我们先明白 期望的意思：
期望 也就是 P*E
而且重要的是 期望这个东西是一个线性的，也就意味着f(a+b)=f(a)+f(b)
也适用于乘法、除法。
所以我们可以拆分到每条边来，来算每一条边的期望，后面的操作也是对某一条进行操作，与这一点不谋而合。
那每条边在所有情况里面被选的概率有多少呢？
1
2 3
4 5 6 7
...........................比如这种，2-5 这条边被选中的概率有多少呢？
总共的种数 是：C（3，n） 大概是1e15左右。
选中2-5的种数：
5 的子树中包含的点 * 2这个连通块中包含的所有点。
我们就可以算出了。
一开始用并查集在写，和sb一样。。。 这可以看做一棵树的情况下，分成： 子树中包含的点num 和 n-num 就可以了。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
const ll mod = 1e9 + 7;
/*
真的是sb 了， 卡了很久，
主要是再看样例： 最后暴力分析了一下。发现不过如此。
我们用一个dfs 扫出来每条边 (... u)-(v....)
u的集合有多少个点， v的集合有多少个点。
这条边的使用次数就是： C(2,set1)*C(1,set2) + C(1,set)*C(2.set2);
然后在想 C(m,n)怎么算的时候发现，这m恒等于3. 还算个P啊
*/
struct edge{
int v,dis;
int i;
edge(int a,int b,int ii){
v=a;
dis=b;
i=ii;
}
};
vector<edge>G[300005];
double ans=0;
double n;
double sum;
double use[300005];
double dist[300005];
int dfs(int u,int pre,int pos){
ll num2=1;
for(int i=0;i<G[u].size();i++){
edge cnt=G[u][i];
int to=cnt.v;
if(to==pre) continue;
num2+=dfs(to,u,cnt.i);
}
ll num1=n-num2; //这里一顿改，分析什么num1的dfs状态， 就是等于n-num2啊
if(pre==0)
return 0;
double cnt=0;
if(num1==1){
cnt+=(double) ( num1*(num2*(num2-1)/2) ) / (sum*1.0);
}
else if(num2==1){
cnt+=(double) ( num2*(num1*(num1-1)/2) ) / (sum*1.0);
}
else{
cnt+=(double) (num2*(num1*(num1-1)/2) +num1*(num2*(num2-1)/2) ) / (sum*1.0);
}
cnt*=2;
use[pos]=cnt;
ans+=use[pos]*dist[pos];
return num2;
}
int du[300005];
int main() {
//freopen("1.txt", "r", stdin);
scanf("%lf",&n);
sum= double ( (n*(n-1)*(n-2) ) /6);
// double temp=100000;
// printf("%lfn",(double) ( temp*(temp-1)*(temp-2) )/6 );
for(int i=1;i<n;i++){
int u,v,d;
scanf("%d %d %d",&u,&v,&d);
G[u].push_back(edge(v,d,i));
G[v].push_back(edge(u,d,i));
dist[i]=d;
du[u]++;
du[v]++;
}
for(int i=1;i<=n;i++){ //这里改了一会，以叶子节点开始扫好处理一些？？？
if(du[i]==1){
dfs(i,0,0);
break;
}
}
int q;
scanf("%d",&q);
while(q--){
int pos;
double d;
scanf("%d %lf",&pos,&d);
ans-= (dist[pos]-d)*use[pos];
dist[pos]=d;
printf("%.7fn",ans);
}
return 0;
}C. Robbers’ watch
这个世界是7进制
告诉你一天有n个小时，每小时m分钟
然后问一天中 的时间显示：
小时：分钟 小时，分钟的长度都符合n,m的长度（在7进制下）
然后同一个字不能出现两次
有点坑，就是7 这个东西长度只算1
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
const double PI = acos(-1.0);
const double e = exp(1.0);
#define ll __int64
template<class T> T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<class T> T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
using namespace std;
const ll mod = 1e9 + 7;
/**
题意很jb蛋疼
我特么读了半天。。。
给你 n,m 两个数
问你 在七进制下 0-n-1 ：0-m-1
有多少对(a,b) 满足 a的长度 = n在7进制下的长度 b同理
满足a:b 每一位上的数都不相同。
别看n,m很大 其实都是瞎搞 ，在七进制下 0.1.2.3.4.5.6 一共就7个数， 只要a+b长度>7 就没有满足条件的数了
*/
int fa[15];
int vis[15];
int n,m;
int lenb,lena;
int poww(int l){
int ans=1;
for(int i=0;i<l;i++)
ans*=7;
return ans;
}
int ans;
int dfsb(int pos, int u, int num) {
// printf("dfsb:%d %d %dn",pos,u,num);
int ans=0;
num += u * poww(lenb - pos);
if (num >= m)
return 0;
if (pos == lenb ) {
return 1;
}
for (int i = 0; i < 7; i++) {
if (vis[i] == 1)
continue;
vis[i] = 1;
ans+=dfsb(pos + 1, i, num);
vis[i]=0;
}
return ans;
}
int dfsa(int pos,int u,int num){
// printf("dfsa:%d %d %dn",pos,u,num);
int ans=0;
num+=u*poww(lena-pos);
// printf("num=%d n=%dn",num,n);
if(num>=n) return 0;
if(pos==lena){
if(num>=n) return 0;
for(int i=0;i<7;i++)
if(!vis[i]){
vis[i]=1;
ans+=dfsb(1,i,0);
vis[i]=0;
}
return ans;
}
for(int i=0;i<7;i++){
if(vis[i]==1) continue;
vis[i]=1;
ans+=dfsa(pos+1,i,num);
vis[i]=0;
}
return ans;
}
int flag[15];
int main() {
//freopen("1.txt", "r", stdin);
scanf("%d %d",&n,&m);
lena=0;
lenb=0;
int nn=n-1;
int mm=m-1;
if(!nn) lena=1;
if(!mm) lenb=1;
while(nn){
nn/=7;
lena++;
}
while(mm){
mm/=7;
lenb++;
}
// printf("%d %dn",lena,lenb);
if(lena+lenb>7){
printf("0n");
return 0;
}
int cnt=0;
for(int i=0;i<7;i++){
memset(vis,0,sizeof(vis));
vis[i]=1;
cnt+=dfsa(1,i,0);
}
printf("%dn",cnt);
return 0;
}最后
以上就是专一砖头为你收集整理的【小题集】临阵磨枪做一些题，锻炼思维，去混杭州了。的全部内容，希望文章能够帮你解决【小题集】临阵磨枪做一些题，锻炼思维，去混杭州了。所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复