A. Arena
題目傳送門：
A. Arena
題目大意：
有n個人，每個人都有戰斗力，當兩個人打起來時，戰斗力高的人贏并且戰斗力加1，當戰斗力達到100500時，則成為英雄，問能有多少人能成為英雄，
思路：
顯而易見，除了戰斗值最低的人之外，其他的所有人都有可能成為英雄，
AC Code
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int num=0;
for(int i=1;i<=n;i++)
if(a[i]!=a[1]) num++;
printf("%d\n",num);
}
//system("pause");
return 0;
}
B. Cat Cycle
題目傳送門：
B. Cat Cycle
題目大意：
貓A會按照 n , n-1 , n-2……3 ，2 ，1，n , n-1……的順序移動
貓B會按照1，2，3，4，……n-1，n，1，2的順序移動，當貓A和貓B處于同一位置時，則貓B向后順延一個位置，隨意兩只貓在任意時刻都不會在同一位置，
思路：
一看資料范圍1e9，那么基本是有規律可循的，
當n為偶數時，我們發現兩只貓一定不會碰到，
當n為奇數時，我們發現當第一次在(n+1)/2的位置相遇之后，兩只貓每過n/2次就會碰到，
計數模擬即可，
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
if(n%2==0)
{
int res=k%n;
if(res==0) res=n;
printf("%d\n",res);
}
else
{
int f=(n+1)/2;
if(k<f) printf("%d\n",k);
else
{
int res=k+1+(k-f)/(f-1);
res=res%n;
if(res==0) res=n;
printf("%d\n",res);
}
}
}
//system("pause");
return 0;
}
C. Minimum Ties
題目傳送門：
C. Minimum Ties
題目大意：
有n只球隊，每兩個球隊之間都會打一場，勝者加三分，輸的不加分，但是如果平局則兩邊個加一分，題目要求平局數量最少，并且每個球隊的總得分相同，
思路：
總局數是sum=（n-1) * n / 2，當n為奇數時sum/n=(n-1)/2,剛好能整除，所以每個隊都勝（n-1)/2場，其他都輸即可，當n為偶數時由于sum/n不能整除，所以我們需要平局，然而我們發現sum%n=n/2，所以兩個隊之間有一個平局，所有隊都加1，分數還是相等的，按照上述意思構造即可，
AC Code
（比賽時候代碼寫的可能比較亂，建議自己手寫幾個例子構造看看，找一下規律）
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n%2==1)
{
int f=(n-1)/2;
int num=n-1;
for(int i=1;i<n;i++)
{
for(int j=1;j<=num;j++)
{
if(j<=f) printf("1 ");
else printf("-1 ");
}
num--;
}
printf("\n");
}
else
{
if((n/2)%2==1)
{
int f=(n-1)/2;
for(int i=1;i<n;i++)
{
int cnt=0;
for(int j=i+1;j<=n;j++)
{
if(i%2==1&&j==i+1) printf("0 ");
else if(cnt<f)
{
printf("1 ");
cnt++;
}
else printf("-1 ");
}
}
printf("\n");
}
else
{
int f=(n-1)/2;
for(int i=1;i<n;i++)
{
if(i!=1&&i%2==1) f--;
int cnt=0;
for(int j=i+1;j<=n;j++)
{
if(i%2==1&&j==i+1)
{
printf("0 ");
continue;
}
if(i%2==1)
{
if(cnt<f)
{
cnt++;
printf("1 ");
}
else printf("-1 ");
}
else
{
if(cnt<f)
{
cnt++;
printf("-1 ");
}
else printf("1 ");
}
}
}
printf("\n");
}
}
}
//system("pause");
return 0;
}
D. Pythagorean Triples
（我覺得D比C簡單多了…）
題目傳送門：
D. Pythagorean Triples
題目大意：
找出滿足
- c = a2 - b
- c2=a2+b2
- 1<=a<=b<=c<=n
的三角形的數量，
思路：
把公式1帶到2里就得到
b(b+1)=c(c-1)
那么顯然只有相鄰的兩個數c=b+1才可能滿足上述式子
且有b+c=a2，那么也就是2*b+1=a2，
那么只要在sqrt(n)的范圍內列舉a即可，
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int sum=0;
for(int i=2;i<=sqrt(2*n-1);i++)
{
int k=i*i;
int ans=0;
if(k%2==1)
{
ans=(k-1)/2;
if(ans>=i) sum++;
}
}
printf("%d\n",sum);
}
//system("pause");
return 0;
}
E. Cheap Dinner(補題)
題目傳送門：
E. Cheap Dinner
題目大意：
一個好的晚飯包含第一道菜，第二道菜，一杯飲料和甜品，每種食物有ni種，對應的價格為ai，bi，ci，di，但是有m1個關系表示第一種食物的第i個和第二種食物的第j個之間不相容，所以你不能同時選擇這兩種食物，同時還有第二種和第三種之間的關系m2，第三種和第四種之間的關系m3，題目問能不能每種食物來一份并且使價錢最少，
思路：
因為限制只在相鄰的兩種食物之間，所以我們可以把這個問題分割成三個子問題：對于每種第二種食物來說，與他能在一起且價格最低的食物是誰，對于第三種和第四種同理求即可，最后把答案合并起來，那么如何找最小值，并且在限制關系中又可以有洗掉的操作呢，這時候就可以自然想到map存盤了，具體程序看代碼，
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=150000+10;
const LL INF=1e18;
LL n[5],a[5][N];
vector<int>fac[N];
map<LL,int>mp;
int main()
{
for(int i=1;i<=4;i++) scanf("%d",&n[i]);
for(int i=1;i<=4;i++)
for(int j=1;j<=n[i];j++)
scanf("%lld",&a[i][j]);
for(int i=2;i<=4;i++)
{
int m;
scanf("%d",&m);
mp.clear();
for(int j=1;j<=n[i];j++) fac[j].clear();
for(int j=1;j<=n[i-1];j++)
{
if(a[i-1][j]==INF) continue;
mp[a[i-1][j]]++;
}
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
if(a[i-1][u]==INF) continue;
fac[v].push_back(u);
}
for(int j=1;j<=n[i];j++)
{
for(auto &f:fac[j])
{
mp[a[i-1][f]]--;
if(mp[a[i-1][f]]==0) mp.erase(a[i-1][f]);
}
if(mp.empty()) a[i][j]=INF;
else a[i][j]+=(*mp.begin()).first;
for(auto &f:fac[j]) mp[a[i-1][f]]++;
}
}
LL res=INF;
for(int i=1;i<=n[4];i++)
res=min(res,a[4][i]);
if(res==INF) printf("-1\n");
else printf("%lld\n",res);
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/260291.html
標籤：其他
上一篇：字串操作函式和記憶體函式詳解