存一下代码
A. Alternative Architecture
就是算一下斜边一定下的直角三角形个数，需要注意的是斜边并不是 a 和 b ，而是 a − 1 和 b − 1 ，复杂度要求不高，暴搜即可
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
ll a,b;
cin>>a>>b;
if(a>b)
swap(a,b);
a-=1,b-=1;
ll cnt=0;
for(ll i=1;i<a;i++)
{
if(b*i%a!=0)
continue;
ll s=sqrt(a*a-i*i);
if(s*s+i*i==a*a)
{
if(s*b%a==0)
cnt++;
}
}
if(a==b)
cout<<cnt+1<<'\n';
else
cout<<cnt*2+2<<'\n';
return 0;
}
C. Chaotic Construction
只需查看两个方向上是否有障碍物即可，直接查询复杂度会爆，用树状数组优化
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int tree[N];
void update(int x,int d)
{
while(x<=n)
{
tree[x]+=d;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
int q;
cin>>n>>q;
memset(tree,0,sizeof(tree));
for(int i=1;i<=q;i++)
{
char op;
int a;
cin>>op>>a;
if(op=='-')
update(a,1);
else if(op=='+')
update(a,-1);
else if(op=='?')
{
int b;
cin>>b;
if(a>b)
swap(a,b);
if((sum(a)==0&&(sum(n)-sum(b-1)==0))||sum(b)-sum(a-1)==0)
cout<<"possible"<<'\n';
else
cout<<"impossible"<<'\n';
}
}
return 0;
}
E. Enjoyable Entree
a0 = 0 , a1 = 1 ,
用特征方程可以直接解出来 an 的通式:
AC代码： 1
2
3
4
5
6
7
8
9
10
11
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
ll n;
scanf("%ld",&n);
long double ans2=4.0/3*pow(-0.5,n)+2.0/3;
printf("%Lf %Lf\n",(1-ans2)*100,ans2*100);
return 0;
}
I. Improving IT
如果将 arc[i][j] 当做从第 i 个月买入CPU开始经历 j 个月之后将CPU卖掉所需成本，那么这个题就是求 1, 2, ..., n + 1 这些点组成的图中从 1 到 n + 1 的最短路径
记忆化搜索即可，复杂度为 O(m⋅n) 符合要求
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
typedef long long ll;
const int N=5e6;
int n,m;
int arc[N];
ll dp[N];
int num(int x,int y)
{
return x*(m+2)+y;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
memset(arc,-1,sizeof(arc));
for(int i=1;i<=n;i++)
{
int c;
cin>>c;
for(int j=1;j<=min(m,n+1-i);j++)
{
int cj;
cin>>cj;
arc[num(i,j)]=c-cj;
}
}
for(int i=1;i<=n+1;i++)
dp[i]=LONG_LONG_MAX;
dp[0]=dp[1]=0;
for(int i=1;i<=n+1;i++)
{
for(int j=max(1,i-m);j<i;j++)
{
dp[i]=min(dp[i],dp[j]+arc[num(j,i-j)]);
}
}
cout<<dp[n+1]<<'\n';
return 0;
}
K. K.O. Kids
一个模拟
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
string s;
cin>>s;
int i=0;
int cnt=0;
int op=0;
while(i<s.length())
{
if(op==0)
{
if(s[i]=='L')
i++;
else
{
i++;
cnt++;
op=(op+1)%2;
}
}
else
{
if(s[i]=='R')
i++;
else
{
i++;
cnt++;
op=(op+1)%2;
}
}
op=(op+1)%2;
}
cout<<max(0,k-cnt)<<'\n';
return 0;
}
L. Lots of Land
可以看出有解的话每一块的面积 S ∣ l ⋅ w 。
并且 S ∣ l ⋅ w 时一定有解。
如果 S 是素数，那么显然可以；如果 S 不是素数，那么可以选择 S 与 min(l,w) 的最小的公约数作为矩形的短边，然后用仿射变换将短边变回1，重复这个过程，可知 S 不为素数时与 S 为素数时结果一样。
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
typedef long long ll;
const int N=105;
char ch[N][N];
int main() {
ios::sync_with_stdio(false);
int l,w,n;
cin>>l>>w>>n;
if(l*w%n!=0)
cout<<"impossible"<<'\n';
else
{
int s=l*w/n;
int x=1,y=1;
for(int i=1;i<=s;i++)
{
if(s%i!=0)
continue;
if(l%i==0&&w%(s/i)==0)
{
x=i,y=s/i;
break;
}
}
char c='A';
//cout<<x<<' '<<y<<'\n';
for(int i=0;i<l;i++)
{
for(int j=0;j<w;j++)
{
ch[i][j]=c+j/y;
}
if((i+1)%x==0)
c+=w/y;
}
for(int i=0;i<l;i++)
{
for(int j=0;j<w;j++)
cout<<ch[i][j];
cout<<'\n';
}
}
return 0;
}