鴿了建模隊友的一晚,悄悄地寫個
a
t
c
o
d
e
r
atcoder
atcoder沒人發現吧?
悄悄地
a
k
ak
ak,不讓他們發現
AtCoder Beginner Contest 190
- A.Very Very Primitive Game
- 題目大意:
- 題目思路:
- Code:
- B.Magic 3
- 題目大意:
- 題目思路:
- Code:
- C.Bowls and Dishes
- 題目大意:
- 題目思路:
- Code:
- D.Staircase Sequences
- 題目大意:
- 題目思路:
- Code:
- E.Magical Ornament
- 題目大意:
- 題目思路:
- Code:
- F.Shift and Inversions
- 題目大意:
- 題目思路:
- Code:
A.Very Very Primitive Game
題目大意:
略
題目思路:
略(水題)
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e5+700;
const int M = 1e6+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
ll a,b,c;read(a);read(b);read(c);
if(c == 0){
if(a>b) printf("Takahashi\n");
else printf("Aoki\n");
}else{
if(b>a) printf("Aoki\n");
else printf("Takahashi\n");
}
return 0;
}
/**
**/
B.Magic 3
題目大意:
判斷當前給出 s , t s,t s,t中是否存在 s < S s \lt S s<S, t < D t \lt D t<D的物品
題目思路:
水題
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e5+700;
const int M = 1e6+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int main(){
ll S,D;
read(n);read(S);read(D);
int f = 0;
for(int i=1;i<=n;i++){
int x,y;read(x);read(y);
if(x<S && y>D) f = 1;
}
printf("%s\n",f?"Yes":"No");
return 0;
}
/**
5
N 83 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
83
**/
C.Bowls and Dishes
題目大意:
現在有 N N N個盤子
給出一些條件 ( A i , B i ) (A_i,B_i) (Ai?,Bi?),這個條件被滿足當且僅當 A i , B i A_i,B_i Ai?,Bi?盤子中都有一件物品
現在有 K K K個人,可以向 C i , D i C_i,D_i Ci?,Di?中放一個物品,不能同時放只能放一個,問最多能滿足幾個條件?
題目思路:
主要考慮到 K ≤ 17 K \le 17 K≤17,所以直接暴力列舉 K K K的狀態就好了
復雜度: O ( N ? 2 K ) O(N*2^K) O(N?2K)
暴力判斷每個狀態的結果,最后求最優就好了,
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e6+700;
const int M = 2e5+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct node{
int x,y;
}q[maxn];
ll dp[maxn][20];///前i個線段形成以K結尾時最小長度
ll c[maxn];
ll w[maxn][2];
int vis[maxn];
int main(){
read(n);read(m);
for(int i=1;i<=m;i++){
read(q[i].x);
read(q[i].y);
}
read(p);
for(int i=0;i<p;i++){
read(w[i][0]);
read(w[i][1]);
}
int MAX = (1<<p);
int ans = 0;
for(int i=0;i<MAX;i++){
for(int k=0;k<p;k++){
int op = (i>>k&1);
vis[w[k][op]] = 1;
}
int res = 0;
for(int k=1;k<=m;k++){
if(vis[q[k].x] && vis[q[k].y])
res++;
}
ans = max(ans,res);
for(int k=1;k<=n;k++) vis[k] = 0;
}
di(ans);
return 0;
}
/**
5
N 83 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
83
**/
D.Staircase Sequences
題目大意:
詢問有多少公差為1的序列的是 N N N
題目思路:
公式題,首先看見資料范圍 N ≤ 1 e 12 N \le 1e12 N≤1e12,考慮直接根號分解
推一下公式:
假設存在一段序列 [ l + 1 , r ] [l+1,r] [l+1,r]和是 N N N,那么滿足:
r ? ( r + 1 ) 2 ? l ? ( l + 1 ) 2 = N \frac{r*(r+1)}{2} - \frac{l*(l+1)}{2} = N 2r?(r+1)??2l?(l+1)?=N
r ? ( r + 1 ) ? l ? ( l + 1 ) = 2 ? N r*(r+1)-l*(l+1)=2*N r?(r+1)?l?(l+1)=2?N
r ? r ? l ? l + r ? l = 2 ? N r*r - l*l +r-l = 2*N r?r?l?l+r?l=2?N
( r ? l ) ? ( r + l ) + ( r ? l ) = 2 ? N (r-l)*(r+l)+(r-l) = 2*N (r?l)?(r+l)+(r?l)=2?N
( r ? l ) ? ( r + l + 1 ) = 2 ? N (r-l)*(r+l+1) = 2*N (r?l)?(r+l+1)=2?N
根號分解因子,之后判斷即可
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e5+700;
const int M = 1e6+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
map<pair<ll,ll>,int>mp;
int main(){
read(n);
n*=2;
ll ans = 0;
for(ll i=1;i*i<=n;i++){
if(n%i == 0){
ll tempx = i,tempy = n/i;
if((tempx+tempy-1)%2==0){
ll r = (tempx+tempy-1)/2;
ll l = (r-tempx);
if(!mp[{l,r}]){
mp[{l,r}] = 1;
ans ++;
}
}
tempy = i,tempx = n/i;
if((tempx+tempy-1)%2==0){
ll r = (tempx+tempy-1)/2;
ll l = (r-tempx);
if(!mp[{l,r}]){
mp[{l,r}] = 1;
ans ++;
}
}
}
}
dl(ans);
return 0;
}
/**
5
N 83 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
83
**/
E.Magical Ornament
題目大意:
給你 M M M個相連的數對,在生成的序列中只能用 M M M個相連的數對連接(數對不考慮順序),
給出
K
K
K個數,問包含K個數的 最小的 可以連接的 序列長度是多少
題目思路:
首先可以將數抽象為點,那么以 s s s開始以 t t t結束最少的序列長度,就可以由最短路求出,
所以首先預處理 K K K個點之間兩兩之間的最短路,
有了這個之后,觀察K的范圍 K ≤ 17 K \le 17 K≤17,所以直接最小權值哈密爾頓回路就好了.
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e16+7;
const ll maxn = 1e6+700;
const int M = 2e5+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll dis[maxn];
struct N{
int id;
ll w;
bool friend operator<(N a,N b)
{
return a.w>b.w;
}
};
vector<pair<int,int>>v[maxn];
void dijstra(int st){
for(int i=1;i<=n;i++) dis[i]=INF;
dis[st]=0;
N s;s.id=st;s.w=0;
priority_queue<N>q;
q.push(s);
while(!q.empty()){
N u=q.top();q.pop();
if(dis[u.id]!=u.w) continue;
for(auto x:v[u.id]){
int e = x.first,w = x.second;
if(dis[e]>u.w+w){
dis[e]=u.w+w;
N now;now.id=e;
now.w=dis[e];
q.push(now);
}
}
}
return ;
}
ll c[maxn];
ll mp[20][20];
ll s[20][1<<18];
int main(){
read(n);read(m);
for(int i=1;i<=m;i++){
int x,y;read(x);read(y);
v[x].push_back({y,1});
v[y].push_back({x,1});
}
read(p);
for(int i=1;i<=p;i++) read(c[i]);
for(int i=1;i<=p;i++){
dijstra(c[i]);
for(int k=i+1;k<=p;k++){
mp[i-1][k-1] = mp[k-1][i-1] = dis[c[k]];
}
}
int MAX = 1<<p;
for(int i=0;i<p;i++)
for(int k=0;k<MAX;k++)
s[i][k] = INF;
for(int i=0;i<p;i++) s[i][1<<i] = 0;
for(int i=1;i<MAX;i++){
for(int k=0;k<p;k++){
for(int j=0;j<p;j++){
if(j == k) continue;
if(i>>j&1) continue;
s[j][i|(1<<j)] = min(s[j][i|(1<<j)],s[k][i]+mp[k][j]);
}
}
}
ll ans = INF;
for(int i=0;i<p;i++)
ans = min(ans,s[i][MAX-1]);
if(ans>=INF) printf("-1\n",ans);
else printf("%lld\n",ans+1);
return 0;
}
/**
5
N 83 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
83
**/
F.Shift and Inversions
題目大意:
初始給出一個序列 N N N,可以看成一個環,
輸出 N N N行:
第 i i i行代表從 i i i開始 N N N個數字的序列逆序對數,
題目思路:
首先將i = 1的逆序對數求出
觀察接下來的變化,每次移動都是將第1個放到最后
也就是說:
- 減少小于它的數字個數的逆序對數:因為他要放到最后,之前比他大的都要減少 1 1 1
- 增加大于它的數字個數的逆序對數:因為他要放到最后,前面的比他大的要增加 1 1 1
問題就解決啦,
Code:
/*** keep hungry and calm CoolGuang! ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<hash_map>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e5+700;
const int M = 1e6+8;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll a[maxn];
ll sum[maxn];
void add(int pos){
while(pos<=n){
sum[pos]++;
pos += pos&-pos;
}
}
ll query(int pos){
ll ans = 0;
while(pos){
ans += sum[pos];
pos -= pos&-pos;
}return ans;
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
a[i]++;
}
ll ans = 0;
for(int i=1;i<=n;i++){
ans += query(n)-query(a[i]);
add(a[i]);
}
dl(ans);
for(int i=1;i<=n;i++){
ans += query(n)-query(a[i])-query(a[i]-1);
dl(ans);
}
return 0;
}
/**
5
N 83 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
83
**/
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/254832.html
標籤:其他
上一篇:QGLViewer+Qt5+VS2017開發環境搭建
下一篇:Educational Codeforces Round 103 (Rated for Div. 2) D Journey
