這個在codeforces的題目編號是424A-424E
424A，Squats
題目意思：
就是給你n個人，X表示站著，x表示坐著
你在一秒可以讓一個人站著或坐著
給你n個人的狀態，問你要幾秒可以讓一般人站著，並輸出改變後的結果，很水，不想多說
#include
#include
using namespace std;
const int maxn = 200+20;
bool flag[maxn];
char s[maxn];
int n,cnt;
int main()
{
while(~scanf(%d,&n))
{
cnt = 0;
scanf(%s,s);
for(int i=0;i0)
{
printf(X);
ca--;
}
else
printf(%c,s[i]);
}
printf(
);
}
else
{
int ca = cnt-n/2;
printf(%d
,ca);
for(int i=0;i0)
{
printf(x);
ca--;
}
else
printf(%c,s[i]);
}
printf(
);
}
}
}
return 0;
}
424B，Megacity
題目地址：http://codeforces.com/problemset/problem/424/B
題目大意：
你在（0，0）位置上，已經有了s個人，但是你需要1000000個人，你需要擴展
然後你周圍的城市的坐標和人告訴你，問你抽氣這麼多人，需要擴張多大
解題思路：
把周圍的按半徑排序，然後一個一個加，加夠了就break
#include
#include
#include
#include
using namespace std;
const double eps = 1e-10;
const int maxn =1000+20;
const int billion = 1000000;
int n;
struct pp
{
int x,y,k;
double r;
};
pp p[maxn];
bool cmp(pp a,pp b)
{
return a.r= billion)
{
ans = p[i].r;
break;
}
}
if(ans<0)
printf(-1
);
else
printf(%.8lf
,ans);
}
return 0;
}
424C，Magic Formulas
題目地址：http://codeforces.com/problemset/problem/424/C
題目意思：
給你p1,p2,...,pn
然後定義：
要你求Q
解題思路：
我們發現異或是滿足交換律的，所以首先可以是p1^p2^p3^...^pn
然後再就是後面的mod之後的異或
我們發現可以歸納為(1%i)^(2%i)^(3%i)^...^(n%i)，i from 1 to n
那麼對於一個i來說，上面就為1^2^3^...^(i-1)^0 這樣的一個循環，最後再加上一個尾巴
這樣如果前面的循環是偶數就是0了，如果是奇數個，就是他本身，最後再異或上那個尾巴就可以了，這裡可以先預處理一下
對於每個i我們都這麼求，就可以解決了
#include
#include
#include
#include
using namespace std;
const int maxn = 1000000+20;
int xor_n[maxn];
int p[maxn];
int n;
int q;
void init()
{
xor_n[0]=0;
for(int i=1;i
424D，Biathlon Track
題目地址：http://codeforces.com/problemset/problem/424/D
題目大意：
給你一個N×M的矩陣，上面有數字，從大的到小的要花費td，從小的到大的要花費tu，大小一樣花費tp
要你這一個順時針的圈，使這個花費加起來最接近t，四個邊都要>=3
解題思路：
這是第一種方法，比較暴力，先預處理從4個方向到自己的花費
然後枚舉4個點用O（1）算，注意這裡abs最後自己寫，並且只用一次，用多了就TLE了
#include
#include
#include
#include
using namespace std;
const int maxn=300+10;
struct node
{
int up,down,left,right;
int height;
};
node ma[maxn][maxn];
int n,m;
int tp,tu,td,t;
inline int abs2(int x) {
if (x < 0) x = -x;
return x;
}
int main()
{
while(~scanf(%d%d%d,&n,&m,&t))
{
scanf(%d%d%d,&tp,&tu,&td);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf(%d,&ma[i][j].height);
ma[i][j].up = ma[i][j].down = ma[i][j].left = ma[i][j].right = 0;
if(i!=1)
{
if(ma[i-1][j].height < ma[i][j].height)
{
ma[i][j].up = ma[i-1][j].up + tu;
}
else if(ma[i-1][j].height > ma[i][j].height)
{
ma[i][j].up = ma[i-1][j].up + td;
}
else
ma[i][j].up = ma[i-1][j].up + tp;
}
if(j!=1)
{
if(ma[i][j-1].height < ma[i][j].height)
{
ma[i][j].left = ma[i][j-1].left + tu;
}
else if(ma[i][j-1].height > ma[i][j].height)
{
ma[i][j].left = ma[i][j-1].left + td;
}
else
ma[i][j].left = ma[i][j-1].left + tp;
}
}
}
for(int i=n;i>=1;i--)
{
for(int j=m;j>=1;j--)
{
if(i!=n)
{
if(ma[i+1][j].height < ma[i][j].height)
{
ma[i][j].down = ma[i+1][j].down + tu;
}
else if(ma[i+1][j].height > ma[i][j].height)
{
ma[i][j].down = ma[i+1][j].down + td;
}
else
ma[i][j].down = ma[i+1][j].down + tp;
}
if(j!=m)
{
if(ma[i][j+1].height < ma[i][j].height)
{
ma[i][j].right = ma[i][j+1].right + tu;
}
else if(ma[i][j+1].height > ma[i][j].height)
{
ma[i][j].right = ma[i][j+1].right + td;
}
else
ma[i][j].right = ma[i][j+1].right + tp;
}
}
}
int ar1,ar2,ac1,ac2;
bool f=false;
int ans = 2000000000;
for(int r1=1;r1<=n;r1++)
{
for(int c1=1;c1<=m;c1++)
{
for(int r2=r1+2;r2<=n;r2++)
{
for(int c2=c1+2;c2<=m;c2++)
{
int tmp = abs(t- (ma[r2][c2].up - ma[r1][c2].up + ma[r1][c2].left - ma[r1][c1].left
+ ma[r2][c1].right - ma[r2][c2].right + ma[r1][c1].down - ma[r2][c1].down));
if(tmp < ans)
{
ans = tmp;
ar1 = r1;
ar2 = r2;
ac1 = c1;
ac2 = c2;
}
}
}
}
}
printf(%d %d %d %d
,ar1,ac1,ar2,ac2);
// printf(ans %d
,ans);
}
return 0;
}
還有一種更效率的方法以及最後一題我後面再更新。
