文章目錄
- 1.明明的亂數
- 2.回文日期
- 3.校門外的樹
- 4.數學考試
- 5.Subsequence
- 6.字串
- 7.丟手絹
- 8.拼數
- 9.紀念品分組
- 10.國王的游戲
- 11.鋪地毯
- 12.「土」巨石滾滾
- 13.Protecting the Flowers
- 14.毒瘤xor
- 15.奇♂妙拆分
- 16.Quasi Binary
- 17.「土」秘法地震
1.明明的亂數
鏈接
題目大意就是：輸入n個1到1000之內的數，然后去重排序輸出，即可
#include<bits/stdc++.h>
using namespace std;
set<int> s; //set集合自動排序去重
int n , num;
int main(){
cin>>n;
while(n--){
cin>>num;
s.insert(num);
}
cout<<s.size()<<endl;
for(auto& ans :s ){
cout<<ans<<" ";
}
}
2.回文日期
鏈接
題目大意就是：給你兩個日期，判斷兩個日期中有多少個日期是回文的（20100102）
因為需要回文，20100102我們可以發現月份和日期反過來就可以得到年份2010，我們只需要判斷反過來的年是否在兩個日期之間即可，
#include<bits/stdc++.h>
using namespace std;
int day[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31}; //每月對應的天數
int ans;
int main(){
int yy,mm,dd;
int y,m,d;
scanf("%4d%2d%2d",&y,&m,&d);
scanf("%4d%2d%2d",&yy,&mm,&dd);
for(int i=1;i<13;i++){
for(int j=0;j<=day[i];j++){
// 0131 ---> 1310
int year = j%10*1000+j/10*100+i%10*10+i/10;
if(year>=y && year<=yy) ans++;
}
}
cout<<ans<<endl;
}
3.校門外的樹
鏈接
題目大意：在0-N的區間都是樹，現在要移除一些區間，求剩余樹的個數，直接數軸模擬即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int N,M,ans;
struct node{
int L,R;
}x[maxn];
bool cmp(struct node a , struct node b){
if(a.L!=b.L) return a.L<b.L;
return a.R<b.R;
}
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>x[i].L>>x[i].R;
}
sort(x,x+M,cmp);
for(int i=0;i<M;i++){
if(i==0) {ans = ans+(x[i].R-x[i].L+1) ;continue;}
if(x[i].L<=x[i-1].R){
if(x[i].R<=x[i-1].R){
x[i].R = x[i-1].R;
continue;
}
ans = ans+(x[i].R - x[i-1].R); //x[i].L這個點已經減去了，不用+1
}else ans = ans+(x[i].R - x[i].L+1);
}
cout<<(N+1)-ans<<endl;
/*
500 3
0 300
100 200
300 500
*/
}
4.數學考試
鏈接
題目大意就是n個題目，選取2k個題，并且獲得的分數盡可能的大，他準備選2個不連續的長度為k的區間,即[L,L+1,L+2,…,L+k-1]，[R,R+1,R+2,…,R+k-1]（R >= L+k），由于兩段之間是不連續的，但是每段里面的分數是連續的，我們可以用一個陣列維護前i個分數之和，然后貪心，取得最大的分數，
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const long long Max = 1e18;
long long a[maxn];
int main(){
int t;
cin>>t;
while(t--){
memset(a,0,sizeof(a));
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i] = a[i]+a[i-1];
}
long long l = -Max , r = -Max;
for(int i=k;i+k<=n;i++){
l = max(l , a[i]-a[i-k]);
r = max(r , l+a[i+k]-a[i]);
}
cout<<r<<endl;
}
}
5.Subsequence
鏈接
題目大意：給定長度為n的整數數列以及整數S，求出總和不小于S的連續子串的長度的最小值，如果解不存在，輸出0，直接用一個陣列維護前綴和，然后得出解
#include<iostream>
using namespace std;
typedef long long ll;
int T,n,x;
ll s;
int solve(){
int ans = 0x3f3f3f3f,f=0;
ll sum[100010]={0}; //前綴和
for(int i=1;i<=n;i++){
cin>>x;
sum[i] = sum[i-1]+x;
if(sum[i]>s) f=1;
if(x>s) ans = 1;
}
if(ans==1) return ans; //存在一個數字直接大于S
if(f==0) return 0; //所有數字和都小于S
for(int i=0,r=1;r<=n;){
if(sum[r]-sum[i]<s) r++;
else {
ans=min(ans,r-i); //得到最小的區間
i++;
}
}
return ans;
}
int main(){
cin>>T;
while(T--){
cin>>n>>s;
cout<<solve()<<endl;
}
}
6.字串
鏈接
題目大意：給出字串 S ， 問最短的 一個子串包含 26 個字母的子串的長度
用尺取法，一個游標記錄區間的開始，一個記錄區間的末尾，每次讀取 r 右移，左邊的出現過則 l 右移，如果cnt為26，更新答案
#include<bits/stdc++.h>
using namespace std;
int vis[27];
int ans=0x3f3f3f3f , cnt, l ;
int main(){
string s;
cin>>s;
for(int r=0;r<s.length();r++){
if(!vis[s[r]-'a']) cnt++;
vis[s[r]-'a']++;
while(vis[s[l]-'a']>1){
vis[s[l]-'a']--;
l++;
}
if(cnt==26) ans = min(ans , r-l+1);
}
cout<<ans<<endl;
}
7.丟手絹
鏈接
題目大意就是n個小朋友圍城一個圈圈，求任意兩個小朋友之間最遠的距離，距離可以是逆時針也可以是順時針，方法其實也是一樣尺取法，模擬可以發現，兩個小朋友之間的距離先是越來越遠然后超過總距離一半的時候越來越近
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int main()
{
int n,a[maxn],totalLen = 0;
cin>>n;
for(int i = 0 ; i < n; i++)
{
scanf("%d",&a[i]);
totalLen += a[i]; //總距離
}
int maxLen = 0;
int curLen = 0;
int index = 0;
for(int i = 0; i < n ; i++)
{
while(curLen<totalLen/2)
{
curLen += a[index];
index ++;
index %= n;
if(curLen<=totalLen/2) maxLen = max(maxLen,curLen);
}
curLen -= a[i];
}
cout<<maxLen<<endl;
return 0;
}
8.拼數
鏈接
題目大意就是給你n個正整數，拼成一個數，使其最大，直接模擬，貪心即可…
#include<bits/stdc++.h>
using namespace std;
string a[25];
bool cmp(string a , string b){
return a+b>b+a;
}
int n;
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++) cout<<a[i];
cout<<endl;
}
9.紀念品分組
鏈接
題目大意就是n個物品分組，每組最多兩件，并且兩件之和不能超過一個值，簡單的貪心就好了
// 20 20 30 50 60 70 80 90 90
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30000+3;
int w,n , a[maxn],ans;
int main(){
cin>>w>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int l = 0 , r=n-1;
while(l<=r){
if(a[l]+a[r]<=w) l++,r--;
else r--;
ans++;
}
cout<<ans<<endl;
}
10.國王的游戲
鏈接
題目意思就是n個人與國王站在一排，國王永遠站在第一個，然后每個人的左右手有一個數，每個人得到國王賞賜的金幣是排在自己之前的所有人的左手乘積除以自己右數的數，要是的得到最大獎勵最少，由于資料很大，所以就用java寫，不需要考慮精度問題，此題也是一個貪心，貪心的策略，羽巨已經推理過了，這邊就直接上代碼吧
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class H
{
int l;
int r;
}
class cmp implements Comparator<H>
{
public int compare(H x,H y)
{
return x.l*x.r-y.l*y.r;
}
}
public class Main
{
public static void main(String[] args)
{
int a,b; //國王
Scanner in=new Scanner(System.in);
int n=in.nextInt();
a=in.nextInt();
b=in.nextInt();
H person[]=new H[1003];
int i;
for(i=1;i<=n;i++)
{
person[i]=new H();
person[i].l=in.nextInt();
person[i].r=in.nextInt();
}
//排序
Arrays.sort(person,1,n+1,new cmp());
BigInteger ans=new BigInteger("0");
BigInteger now=BigInteger.valueOf(a);
for(i=1;i<=n;i++)
{
ans=ans.max(now.divide(BigInteger.valueOf(person[i].r)));
now=now.multiply(BigInteger.valueOf(person[i].l));
}
System.out.println(ans);
}
}
11.鋪地毯
鏈接
題目大意就是如題目字面意思…貪心即可，按照面積小的放前面，大的放后面，然后輸出最后覆寫那個點的那塊布…
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+4;
int n ,x,y;
struct node {
int id,a,b,g,k;
int eara;
}bu[maxn];
bool cmp(struct node a , struct node b){
return a.eara<b.eara;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>bu[i].a>>bu[i].b>>bu[i].g>>bu[i].k;
bu[i].eara = bu[i].g*bu[i].k;
bu[i].id = i+1;
}
cin>>x>>y;
sort(bu,bu+n,cmp);
//for(int i=0;i<n;i++) cout<<bu[i].a<<" "<<bu[i].b<<endl;
int f = -1;
for(int i=n-1;i>=0;i--){
if(bu[i].a<=x&&bu[i].b<=y && bu[i].a+bu[i].g>=x && bu[i].b+bu[i].k>=y){
f = bu[i].id;
break;
}
}
cout<<f<<endl;
}
12.「土」巨石滾滾
鏈接
題目大意就如字面意思，按照人類本能貪心的思想，我們會先消除那種比自己小的ai能獲取最大的bi，這樣會使得m最大才能去消除其他的障礙物，即：
先用完所有加穩定性的，同時在此優先選擇ai小的
然后考慮所有減穩定性的，同時優先選擇減穩定性中ai大的
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
typedef long long ll;
ll n,m;
struct node{
ll a,b;
bool operator <(const node &x)
{
if(b-a>=0&&x.b-x.a>=0) return a<x.a;
if(b-a>=0) return 1;
if(x.b-x.a>=0) return 0;
return b>x.b;
}
}x[maxn];
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>x[i].a>>x[i].b;
}
sort(x , x+n);
for(int i=0;i<n;i++) cout<<x[i].a<<" "<<x[i].b<<endl;
int i=0,f = 1;
for(i=0;i<n;i++){
m = m-x[i].a;
if(m<0) {f = 0 ; break;}
m = m+x[i].b;
}
if(f)puts("Yes");
else puts("No");
}
}
13.Protecting the Flowers
鏈接
題目大意就是農夫有n頭牛在吃花，農夫要把牛送回牛舍，所花的時間分別為TI，每頭牛留在花園的吃花量分別為DI，花田上的花最少破壞的數量，
雨巨思想，三式大于一式，排序貪心即可，
// ta / da < tb / db
// ta * db < da*tb
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll d,t;
}a[100010];
ll res,n,s;
int cmp(node a,node b)
{
return a.t*b.d<b.t*a.d;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].t>>a[i].d;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
res+=s*a[i].d; //第一頭牛沒得吃，直接被抬走了
s+=a[i].t*2;
}
cout<<res<<endl;
return 0;
}
14.毒瘤xor
鏈接
題目大意，就是選取一個x然后對一區間所有數亦或和，使其最大，
前綴和 + 位運算 + 貪心 ，具體如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int sum[maxn][32]; //維護前i個數字每一位有多少1
int main(){
int n , data , q , l , r;
cin>>n;
for(int i=1;i<=n;i++){
cin>>data;
for(int j=0;j<31;j++){
sum[i][j] = sum[i-1][j]+((data)>>j&1);
}
}
cin>>q;
while(q--){
ll ans = 0;
cin>>l>>r;
for(int j=0;j<31;j++){
int cnt = sum[r][j] - sum[l-1][j]; //區間數第j位1的個數
int len = r-l+1; //總個數
//使區間和亦或最大，那么如果0多，我們更希望變為1，如果1多我們更希望不變
// 0^1 = 1 1^1 = 0
if(cnt < len-cnt) ans = ans+(1<<j);
}
cout<<ans<<endl;
}
}
15.奇♂妙拆分
鏈接
將一個數能被拆分成多少個不同的自然數，使得這些自然數相乘的值等于被拆分的數，
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, ans,x;
cin >> t;
while(t--)
{
cin >> x;
if (x == 1) cout << "1" << endl;
else{
ans = 2;
for (int i=2;i*i<x;i++){
// 9 16 25 所以小于即可
if(x%i==0)ans++,x/=i;
}
cout << ans << endl;
}
}
}
16.Quasi Binary
鏈接
題目大意就是給你一個數n，分解為x個數，每個數只能由0和1組成，并且x個數相加等于n
例如：123 = 111+11+1
#include<bits/stdc++.h>
using namespace std;
int ans[10], len ,x;
int main()
{
cin>>x;
for (int i = 1; i <= x; i *= 10) {
int temp = x / i % 10;
len = max(len, temp);
for (int j = 1; j <= temp; ++j) ans[j] += i;
}
printf ("%d\n", len);
for (int i = 1; i <= len; ++i) printf("%d\n", ans[i]);
puts("");
}
17.「土」秘法地震
鏈接
題目意思如字面意思…前綴和+容斥的思想
如果我們要算紅色區域，那么就是 s[i][j] - s[i-k][j]-s[i][j-k] + s[i-k][j-k]
因為黃色區域減去了兩次，所以要加回來一次，如果此區域有建筑物，則ans+1
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,k,s[N][N],ans;
char ch;
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+ch-'0';
}
/*
1 1 1 1
1 2 2 2
1 2 2 2
1 2 2 3
*/
for(int i=k;i<=n;i++)
for(int j=k;j<=m;j++)
{
if(s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k]>0)
ans++;
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250750.html
標籤：其他
上一篇：C#繪制中國象棋棋盤
下一篇：位運算(上)