XVII Open Cup named after E.V. Pankratiev. GP of Tatarstan
A. Arithmetic Derivative
形如$p^p(p是質(zhì)數(shù))$的數(shù)的比值為$1$，用$k$個這種數(shù)相乘得到的數(shù)的比值為$k$，爆搜即可。
#include<cstdio>
#include<algorithm>
typedef unsigned long long ll;
int K,cnt,all;ll n,i,q[100000],ans[1000000];
ll po(ll a,ll b){
ll t=1;
while(b--){
if(t>n/a)return n+1;
t*=a;
}
return t;
}
bool isprime(ll n){
for(ll i=2;i<n;i++)if(n%i==0)return 0;
return 1;
}
void dfs(int x,ll y,int k){
if(y>n)return;
//printf("%d %llu %d\n",x,y,k);
if(k==K){
ans[++all]=y;
return;
}
if(x>cnt)return;
dfs(x+1,y,k);
if(y<=n/q[x])dfs(x,y*q[x],k+1);
}
int main(){
scanf("%d%llu",&K,&n);
for(i=2;;i++){
if(po(i,i)>n)break;
if(isprime(i))q[++cnt]=po(i,i);
}
dfs(1,1,0);
printf("%d\n",all);
std::sort(ans+1,ans+all+1);
for(i=1;i<=all;i++)printf("%llu ",ans[i]);
}
B. White Triangle
留坑。
C. New Street
用set維護相同連續(xù)段，每次新增貢獻時利用多項式求冪，刪除貢獻則采用多項式求逆。
D. Clones and Treasures
貪心，每次不滿足條件了就把前面全部舍棄。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e6 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
char s[N];
int n;
int main()
{
while(~scanf("%s", s + 1))
{
n = strlen(s + 1);
int sum = 0, num = 0;
int ans = 0;
for(int i = 1; i <= n; ++i)
{
int val;
if(s[i] == 'H')val = 1;
else val = (s[i] == 'M' ? 0 : -1);
sum += val;
num += (val == 0);
if(sum < 0)
{
sum = num = 0;
}
else
{
gmax(ans, num);
}
}
printf("%d\n", ans);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復(fù)雜度&&優(yōu)化】
*/
E. Space Tourists
當(dāng)$n>k$時答案為$k$。
否則最優(yōu)策略是將$k$個數(shù)平均分成$n-1$組，每組$size(size-1)$個字符串，外加$k$個兩個字符相等的字符串。
F. Matrix Game
最小表示法。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 105, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
char s[N][N];
struct A
{
string s;
bool operator < (const A & b)const
{
return s < b.s;
}
}line[N], list[N];
int main()
{
while(~scanf("%d%d", &n, &m))
{
for(int i = 1; i <= n; ++i)
{
scanf("%s", s[i] + 1);
line[i].s = s[i] + 1;
}
for(int i = 1; i <= m; ++i)
{
string now = "";
for(int j = 1; j <= n; ++j)
{
now = now + s[j][i];
}
list[i].s = now;
}
sort(line + 1, line + n + 1);
sort(list + 1, list + m + 1);
string ans = "";
for(int i = 1; i <= n; ++i)
{
string body = "";
for(int j = n; j >= 1; --j)if(j != i)
{
body = body + line[j].s;
}
for(int j = 0; j < m; ++j)
{
string tmp = line[i].s.substr(j)+body+line[i].s.substr(0, j);
gmax(ans, tmp);
}
}
for(int i = 1; i <= m; ++i)
{
string body = "";
for(int j = m; j >= 1; --j)if(j != i)
{
body = body + list[j].s;
}
for(int j = 0; j < n; ++j)
{
string tmp = list[i].s.substr(j) + body + list[i].s.substr(0, j);
gmax(ans, tmp);
}
}
int g = ans.size();
int st = g - 1;
for(int i = 0; i < g; ++i)if(ans[i] != '0')
{
st = i;
break;
}
cout << ans.substr(st) << endl;
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復(fù)雜度&&優(yōu)化】
2 3
000
001
*/
G. Milkland
留坑。
H. Parallel Relay
假如知道了所有數(shù)，那么可以等效成只有最小值和最大值的情況。
對于每一段，將所有數(shù)翻折到左邊后排序，那么最小值和最大值分別是從左往右的第一個未翻折到右側(cè)和翻折到右側(cè)的，共$O(n)$種情況，枚舉即可。
時間復(fù)雜度$O(n\log n)$。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m,i,j,a[N],b[N],c[N],ans;
inline int cal(int a,int b,int c,int d){
int ret=~0U>>1;
for(int i=0;i<2;i++){
swap(c,d);
ret=min(ret,abs(a-c)+abs(c-d)+abs(d-b));
}
return ret;
}
int solve(int L,int R){
int i,j;
int cnt=0;
for(i=L;i<=R;i++){
c[++cnt]=b[i];
}
for(i=2;i<cnt;i++)c[i]=min(c[i],m-c[i]+1);
sort(c+2,c+cnt);
if(cnt==2)return abs(c[1]-c[2]);
if(cnt==3)return min(abs(c[1]-c[2])+abs(c[2]-c[3]),abs(c[1]-(m-c[2]+1))+abs(m-c[2]+1-c[3]));
int ret=cal(c[1],c[cnt],c[2],c[cnt-1]);
ret=min(ret,cal(c[1],c[cnt],m-c[2]+1,m-c[cnt-1]+1));
for(i=3;i<cnt;i++){
ret=min(ret,cal(c[1],c[cnt],c[2],m-c[i]+1));
ret=min(ret,cal(c[1],c[cnt],m-c[2]+1,c[i]));
}
return ret;
}
int main(){
scanf("%d%d",&n,&m);
n++;
scanf("%d%d",&b[1],&b[n]);
a[1]=a[n]=1;
for(i=2;i<n;i++)scanf("%d%d",&a[i],&b[i]);
for(i=1,j=0;i<=n;i++)if(a[i]==1){
if(j)ans+=solve(j,i);
j=i;
}
printf("%d",ans);
}
/*
5 8
2 6
1 7
2 3
1 1
2 1
5 21
4 15
2 5
2 6
1 2
2 2
10 10
1 10
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
*/
I. Minimum Prefix
二分答案，然后Hopcroft求二分圖最大匹配檢驗。
J. Terminal
$f[i][j]$表示考慮前$i$組，第一輛車上了$j$個人是否可行。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m, K;
int a[N];
int cnt[N], tmp[N];
bitset<N>f[2020];
int main()
{
while(~scanf("%d%d%d", &n, &m, &K))
{
gmin(K, n);
MS(cnt, 0);
MS(tmp, 0);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
++cnt[a[i]];
}
f[0][0] = 1;
int g = 0;
LL ans = 1e18;
for(int i = 1; i <= n; ++i)
{
++tmp[a[i]];
if(tmp[a[i]] == cnt[a[i]])
{
++g;
f[g] = f[g - 1] | (f[g - 1] << cnt[a[i]]);
for(int j = 1; j <= K; ++j)if(f[g][j] && n - j <= K)
{
gmin(ans, (LL)i * j + (LL)n * (n - j));
}
}
}
if(ans == 1e18)ans = -1;
printf("%lld\n", ans);
}
return 0;
}
/*
【trick&&吐槽】
【題意】
【分析】
【時間復(fù)雜度&&優(yōu)化】
*/
K. New Tetris
用線段樹加速模擬即可。
L. Canonical duel
每個炮塔可以將其同行同列的所有炮塔都激活，因此枚舉一個點，然后將上下左右兩個連通塊合并即可。
#include<cstdio>
const int N=2010,M=N*N;
int n,m,i,j,k,id[N][N],cnt,f[M],size[M];
int ans=-1,px,py;
char a[N][N];
int left[N][N],right[N][N],up[N][N],down[N][N];
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void merge(int x,int y){
x=F(x),y=F(y);
if(x==y)return;
f[x]=y;
}
inline void gao(int x,int y){
int A=up[x][y];
if(!A)A=down[x][y];
int B=left[x][y];
if(!B)B=right[x][y];
int ret=size[f[A]];
if(f[A]!=f[B])ret+=size[f[B]];
if(ret>ans)ans=ret,px=x,py=y;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%s",a[i]+1);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)a[i][j]=a[i][j]=='+';
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]){
id[i][j]=++cnt;
f[cnt]=cnt;
}
for(i=1;i<=n;i++)for(j=1;j<=m;j++){
left[i][j]=a[i][j]?id[i][j]:left[i][j-1];
up[i][j]=a[i][j]?id[i][j]:up[i-1][j];
}
for(i=n;i;i--)for(j=m;j;j--){
right[i][j]=a[i][j]?id[i][j]:right[i][j+1];
down[i][j]=a[i][j]?id[i][j]:down[i+1][j];
}
for(i=1;i<=n;i++){
k=0;
for(j=1;j<=m;j++)if(a[i][j]){
if(k)merge(k,id[i][j]);
k=id[i][j];
}
}
for(i=1;i<=m;i++){
k=0;
for(j=1;j<=n;j++)if(a[j][i]){
if(k)merge(k,id[j][i]);
k=id[j][i];
}
}
for(i=1;i<=cnt;i++)size[F(i)]++;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(!a[i][j])gao(i,j);
if(ans<=0)puts("0");else printf("%d\n%d %d",ans,px,py);
}
浙公網(wǎng)安備 33010602011771號