文章目錄
-
- A、 Maximum Element In A Stack
- B、Rolling The Polygon
- C、Caesar Cipher
- D、Take Your Seat
- H、Fight Against Monsters
A、 Maximum Element In A Stack
計蒜客
要點：在棧中進棧、入棧操作，并維護棧中最大值，每次操作過後用最大值*此次操作數n與前一次計算後的值異或，棧為空則輸出0，0與任何數異或都為0，是以沒啥影響。
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma pack(4)
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mid (r+l)*0.5
#define l (d<<1)
#define r ((d<<1)&1)
#define in(c) (c-'0')
#define ch(i) (i+'0')
const int N=5000007;
const int M=2500;
const int inf=0x3f3f3f;
const double eps=1e-6;
const ll mod=530600414;
int n, p, q, m;
ll ans;
int cnt;
ll maxn[N];
vector<ll> ve;
unsigned int SA, SB, SC;
unsigned int rng61() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
for(int i = 1; i <= n; i++)
{
if(rng61() % (p + q) < p)
{
ve.push_back(rng61() % m + 1);
maxn[cnt]=max(maxn[cnt-1],ve.back());//維護棧内最大值
ans=ans^(i*maxn[cnt]);
cnt++;
}
else
{
if(!ve.empty())
{
ve.pop_back();
//cout<<ve.top()<<endl;
cnt--;
maxn[cnt]=0;//清零操作，可省略
ans=ans^(i*maxn[cnt-1]);
}
}
}
}
int main()
{
int t;
int cas=0;
scanf("%d",&t);
while(t--)
{
while(!ve.empty())
{
ve.pop_back();
}//ve.clear()清空上次樣例的操作
ans=0;
cnt=1;
memset(maxn, 0, sizeof(maxn));
gen();
printf("Case #%d: %lld\n",++cas,ans);
}
return 0;
}
B、Rolling The Polygon
計蒜客
每一次旋轉時相當于以轉點（多邊形旋轉時不動的那個點）為圓心，此點到轉點的距離為半徑，旋轉角度為轉點的外角。即給定點到多邊形每個點的距離為旋轉半徑，每個頂點對應外角為旋轉角度。
要點：求外角，注意精度要足夠大，不然最後結果誤差較大。
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#pragma pack(4)
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mid (r+l)*0.5
#define l (d<<1)
#define r ((d<<1)&1)
#define in(c) (c-'0')
#define ch(i) (i+'0')
const int N=57;
const int M=2500;
const int inf=0x3f3f3f;
const double eps=1e-6;
const ll mod=530600414;
pii a[N],ta;
double dis(pii a,pii b)
{
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}//兩點間距離
double sita(pii a,pii b,pii c)
{
return 3.1415926535-acos(((a.first-b.first)*(c.first-b.first)+(a.second-b.second)*(c.second-b.second))/(dis(a, b)*dis(b,c)));
}//求b外角
int main()
{
int t;
int cas=0;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
double ans=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
}
scanf("%d%d",&ta.first,&ta.second);//點坐标
for(int i=0;i<n;i++)
{
ans+=dis(ta,a[i])*sita(a[(i-1+n)%n],a[i],a[(i+1)%n]);
}//弧長：半徑×角
printf("Case #%d: %.3lf\n",++cas,ans);
}
return 0;
}
C、Caesar Cipher
計蒜客
就是一個移位密碼的題，選擇用數組存字母減去’A’的ASCII碼，最後加上’A’，就不用考慮26個字母間的循環問題了。這題隻有大寫字母，少了很多坑。
1、C++
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int s1[51],s2[51],s3[51];
int main(){
int T;
cin>>T;
for(int t=1;t<=T;t++){
int n,m;
cin>>n>>m;
char ch;
for(int i=0;i<n;i++){
cin>>ch;
s1[i]=ch-'A';
}
for(int i=0;i<n;i++){
cin>>ch;
s2[i]=ch-'A';
}
int len=(s2[0]-s1[0])%26;
for(int i=0;i<m;i++){
cin>>ch;
s3[i]=ch-'A';
}
cout<<"Case #"<<t<<": ";
for(int i=0;i<m;i++){
char x=(s3[i]-len+26)%26;
cout<<char(x+'A');
}
cout<<endl;
}
return 0;
}
2、python
t=int(input())
for i in range(t):
n,m=map(int,input().split())
str1=input()
str2=input()
s=input()
dis=ord(str2[0])-ord(str1[0])
print("Case #"+str(i+1)+": ",end="")
for a in s:
print(chr(ord('A')+(ord(a)-ord('A')-dis+26)%26),end="")
print("")
D、Take Your Seat
計蒜客
題解：注意按順序上車的話拿錯号的主人公一直是第一個上，需要讨論他上去做的位子，後一個上車的人如果發現自己位子沒有被占的話一定會按着自己的座位号坐，依此類推，後面的人都會坐在正确的位置上。
舉幾個例子可以很快發現：按順序上飛機，機率一直是1/2（要特判a==0的情況）；
随機時，考慮主人公第幾個上。最後一個上的時候，前面都坐好了，此時一定坐對，機率1/b;其他順序機率都是1/b1/2,舉個例子，第二個上，第一個人有号碼牌，已經坐好了，現在相當于求b-1個人按順序上最後一個人坐對的機率，前面求過了是機率為1/2。
最後得到式子：**(b+1)/(2b)**。
python寫：
map:第一個參數 function 以參數序列中的每一個元素調用 function 函數，傳回包含每次 function 函數傳回值的新清單。
n=int(input())
for i in range(n):#從0開始
a,b=map(int,input().split());#用于一行輸入使用者的多個值
print("Case #"+str(i+1)+": ",end="")
if a > 1:
print("0.500000",end=" ")
else:
print("1.000000",end=" ")
c=(b+1)/(2*b)
print('%.6f' % c)
H、Fight Against Monsters
計蒜客
lower_bound( )和upper_bound( )都是利用二分查找的方法在一個升序排列的數組中進行查找的。
lower_bound( begin,end,num)：從數組的begin位置到end-1位置二分查找第一個大于或等于 num的數字，找到傳回該數字的位址，不存在則傳回end。通過傳回的位址減去起始位址begin,得到找到數字在數組中的下标。
upper_bound( begin,end,num)：不同之處是：查找第一個大于num的數字。
在降序排列數組中，要重載lower_bound()和upper_bound()：lower_bound( begin,end,num,greater() )
題解：傷害值是累加增長的，斐波拉契數列形式，在atk<=10^5題意下，最多到500(打表知)。是以可以找到每個怪物需要多少次打擊（id值）才能死亡，sum存所有活着的怪物的攻擊值，每次打死一隻要更新sum值。
先打a後打b的排序規則是：a,b攻擊值的和 * 打擊a所需次數+b攻擊值 * 打擊b所需次數<a,b攻擊值的和 * 打擊b所需次數+a攻擊值 * 打擊a所需次數
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=1e5+10;
int a[510];
struct node{
int hp,atk,id;
}mst[maxn];
bool cmp(node a,node b){
return (a.atk+b.atk)*a.id+b.id*b.atk<(a.atk+b.atk)*b.id+a.id*a.atk;
}
int main(){
int T;
cin>>T;
for(int i=1;i<=500;i++)
a[i]=a[i-1]+i;
for(int t=1;t<=T;t++){
int n;
long long sum=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>mst[i].hp>>mst[i].atk;
mst[i].id=lower_bound(a+1,a+501,mst[i].hp)-a;//找到能打死此怪物的最小的打擊次數
sum+=mst[i].atk;
}
sort(mst,mst+n,cmp);
long long ans=0;
for(int i=0;i<n;i++){
ans+=sum*mst[i].id;//活着的怪物都會在打死某一隻怪物的過程中攻擊，是以sum*id
sum-=mst[i].atk;//更新打擊總值
}
cout<<"Case #"<<t<<": "<<ans<<endl;
}
return 0;
}
![POJ 2155 Matrix（樹狀數組+單點更新）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)