引流廣西東信杯
“中國東信杯”廣西大學第三屆程式設計競賽（新生組）”
https://ac.nowcoder.com/acm/contest/10172?&headNav=www#rank
密碼：2020gxuacm19
公共題第一題：A++++
題解：判定na和in的最小值，
如果用char string[200]存的話就很簡單了
開兩個計數器，讀string[0]是i或者n
然后求兩個計數器的最小值，總用時八分鐘，主要讀歪題了
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<algorithm>
//這個是大整數，一般打競賽long long不容易爆資料int
#define ll long long
#define N 100000
using namespace std;
int main(){
//關閉流同步，比賽代碼，因為cin比scanf慢，會被time limited exceed
ios::sync_with_stdio(false);
ll n=0;
//等效于scanf("%lld",&n);
cin>>n;
while(n--){
ll t,count1=0,count2=0;
cin>>t;
while(t--){
char s[40];
cin>>s;
if(s[0]=='i')count1++;
if(s[0]=='n')count2++;
}
//等效printf("A");
cout<<'A';
//判定兩個計數器哪個數字小，把小的打進count1
count1=min(count1,count2);
while(count1--){
cout<<'+';
}
cout<<endl;//回車不能丟
}
}
第二題：GDP Carry
博弈論，題目和題面毫無干系的題
推理一個結果，已知先手只能走奇數步，后手只能走偶數步
就可以猜測是和奇偶性有關的博弈，我們大膽討論：
1.如果是總和是奇數，那么龍老板贏定了，因為他一次可以拿完，
2.如果總和是偶數，那么龍老板要怎么樣贏呢？偶數=奇數+奇數
3.而一旦出現了奇數，那么光依靠小西肯定是不能使得剩下的步數變成偶數
也就是說，龍老板必然還可以走一步，
總結：
只要步數中有一個奇數步
那么龍老板必然可以走一步
那么小西就必然不能讓龍老板在他之前停下，龍老板贏
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 1000005
ll x[N]={};
ll sum[N]={};
bool flag=false;
using namespace std;
int main(){
//關閉流同步
ios::sync_with_stdio(false);
ll n=0;
cin>>n;//等效scanf
for(ll i=1;i<=n;i++){
cin>>x[i];
if(x[i]&1)flag=true;
//x[i]&1是判定奇偶的快速方法，比較實用，可以加速60倍
}
if(flag)cout<<"Antinomy"<<endl;
//等效prinf("Antinomy");
else cout<<"XiJam"<<endl;
}
第三題： Interpretability
幾何數學題，已知邊長為1 2 4 8等比數列下去的邊有f1 f2 f3條，求可以組成多少個三角形，
數學有一個三角形的初中結論：a+b>c任意成立，
而在本題中，變成了等腰三角形b>=a，（其中b為腰）
很多人會下意識考慮等邊三角形作為第一種情況，其實大錯特錯，
實際上這題應該把所有等邊三角形看成等腰三角形
舉個例子1 1 1 6，
如果把6條權值為8的邊考慮成等邊就會丟掉三條邊，
而如果考慮成等腰的話，那么值8的邊可以組成三個等腰，和剩下的小邊組成等腰三角形，
因此，這題應當優先考慮等腰的邊，而不是等邊，
#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 1000005
ll x[N]={};
ll sum[N]={};
bool flag=false;
using namespace std;
int main(){
ios::sync_with_stdio(false);
ll n=0,count1=0;
ll count2=0;
ll count3=0;
cin>>n;
for(ll i=1;i<=n;i++){
cin>>x[i];
//利用迭代回圈實作不斷判定等腰三角形存在的情況
while(x[i]>=2&&count2>=1){
count2--;
x[i]-=2;
count1++;
}
//剩下的就變成了底邊，真的等邊三角形
count2+=x[i]%3;
count1+=x[i]/3;
}
cout<<count1<<endl;
}
第四題 ：Batch Normalization 1D
~~真實名字：拿頭模擬題~~
很漂亮的模擬題，程序其實很清晰，而且題目又長又勸退，題面簡單又單純，可惜我沒做對，
稍微講一下題意：模擬這樣一個程序：
1.給二維矩陣和一維矩陣的運算模式，利用運算規則進行精度計算
2.第一步，先求出兩個定矩陣
3.第二步，進入訓練狀態回圈n_b次，將進行兩種運算
其一：求x_hat
其二：求moving_var和moving_mean，這個運算程序就是模擬程序，
4.結束：最后模擬運算一次，列印結果，
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include<cmath>
#include<list>
using namespace std;
long long n, c,n_b;
double eps, mo;
double x[205][205] = {};
double x_hat[500][500] = {};
double moving1[205] = {};
double moving2[205] = {};
double beta[20005] = {};
double gamma1[20005] = {};
double out[205][205] = {};
double t[205] = {};
list<string>s1;
double mxxx[50] = {};
double varx[50] = {};
//主代碼從這里開始
int main() {
cin >> n >> c >> n_b >> eps >> mo;
for (int i = 0;i < n;i++) {
for (int j = 0;j < c;j++) {
cin >> x[i][j];//存x矩陣
}
}
for (int i = 0;i < c;i++) {
cin >> gamma1[i];//存gamma
}
for (int i = 0;i < c;i++) {
cin >> beta[i];//存beta
}
for (int i = 0;i < c;i++) {
cin >> moving1[i];//存moving—mean
}
for (int i = 0;i < c;i++) {
cin >> moving2[i];//存moving-var
}
for (int i = 0;i < c;i++) {
double tmp = 0;
for (int j = 0;j < n;j++) {
tmp += x[j][i];
}
mxxx[i] = tmp / n;//求mu的矩陣
}
for (int i = 0;i < c;i++) {
double tmp = 0;
for (int j = 0;j < n;j++) {
tmp += (x[j][i] - mxxx[i])* (x[j][i] - mxxx[i]);
}
varx[i] = tmp / n;//求var的矩陣
}
//開始訓練
while (n_b--) {
for (int i = 0;i < n;i++) {
for (int j = 0;j < c;j++) {
t[1] = x[i][j] - mxxx[j];
t[2] = varx[j] + eps;
t[2] = sqrt(t[2]);
x_hat[i][j] = t[1] / t[2];//第一種訓練的模擬程序
}
}//第二種訓練的模擬程序*2
for (int j = 0;j < c;j++) {
t[1] = mo * moving1[j];
t[2] = (1.000000 - mo) * mxxx[j];
moving1[j] = t[1]+t[2];
}
for (int j = 0;j < c;j++) {
t[1] = mo * moving2[j];
t[2] = (1.00000 - mo) * varx[j];
moving2[j] = t[1]+t[2];
}
}
//訓練結束，開始最后的運算
for (int i = 0;i < n;i++) {
for (int j = 0;j < c;j++) {
x_hat[i][j] = (x[i][j] - moving1[j]) / sqrt(moving2[j] + eps);
}
}//列印結果out
for (int i = 0;i < n;i++) {
for (int j = 0;j < c;j++) {
out[i][j] = gamma1[j] * x_hat[i][j] + beta[j];
printf("%.4f ", out[i][j]);
}
if (i != n - 1)cout << endl;
}
}
新生組第五題：小西和數字轉換
思維
倒著思考第x個數以內，除y+1位是1，其余為0
如果不是，那么計數器+1，輸出計數器的數字即可，
#include<iostream>
#include<string>
using namespace std;
int main ()
{
string num;
int n,x,y;
cin >> n >> x >> y;
cin >> num;
int ans = 0;
for ( int i = n - x ; i < n; i++ )
{
//兩個判定限制條件，要么倒序y+1是1，其余都不能是1，不滿足就扣錢
if ( ( num[i] == '1' && i != n - y - 1 ) || ( num[i] == '0' && i == n - y - 1 ) )
ans++;
}
cout << ans << endl;
return 0;
}
新生組第六題：小西和拼圖
拼圖，簡單題
判定兩個條件：
其一是m是否會被2整除
其二是是否存在任意拼圖第二個數字和第三個數字相同
滿足這兩個即可，
（據說有一個資料n是讀取失敗了，有的人正確代碼也錯了，那么不改變n可能就給過了，可以去試試）
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
int a, b, c, d;
int k = 0;
while(n)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
if (b == c)
{
k = 1;
}
n--;
}
if (k == 1 && m % 2 == 0)
printf("YES\n");
else printf("NO\n");
}
return 0;
}
新生組第七題：小西和復制粘貼
~~您就是cv工程師？！~~
這題是經典的倒敘思維題利用倒序由果導因
已知我們要第i個字母
我們從最后一步往前走走到起點不就知道我們需要第i個字符了么，
//您就是cv工程師？？！
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include<list>
using namespace std;
long long n, k,m;
char s[2000005] = {};
long long x[200005] = {};
long long sum[200006] = {};
long long a[200005] = {};
long long b[200005] = {};
long long c[200005] = {};
list<string>s1;
//剛開始思考用鏈表然后發現爆了就沒寫下去
typedef struct node {
string s;
node *x;
}T,*tree ;
int main() {
cin >> k >> m;
cin >> s;
cin >> n;
//倒過來取步驟，方便正向進行，~i就是取反，判定是否i為0
//這么妖的代碼一看就是抄lmgg的
for (long long i = n-1;~i;i--) {
cin >> a[i] >> b[i] >> c[i];
}
for (long long i = 0;i < k;i++) {
long long p = i;//你現在要找第i個數字是哪個字符
for (long long j = 0;j < n;j++) if(c[j]<=p){
long long tmp = b[j] - a[j];
if (c[j] + tmp > p)p = a[j] + p - c[j];
else p -= tmp;
}//那就倒退回去，如果比p大了，那么肯定不影響p的生活
//如果比p小了，要么取代了p，要么讓p這個位置往前了，
//（建議自己手擼一下很快的）
cout << s[p];
}
}
新生組防ak： 小西和秀苑醬餅
這題是真的好題，就算放到正式組也是屈指可數的過題量
模擬+dfs，不愧是龍老板
感謝龍老板提供題解！
#include <bits/stdc++.h>
using namespace std;
#define N 510
#define INF 0x3f3f3f3f//最大值
int n, m, num, ans[N][N], vis[N][N];
char s[N][N];
void F(int x, int y, int z)//dfs（深度優先搜索）
{
if (x < 1 || x > n || y < 1 || y > m || vis[x][y] > 0)
return;//遞回邊界，如果出現了如上情況，那么直接終止
if (vis[x][y] == -1)//如果出現訪問過并且未知可不可以走下去的情況，那么標記無窮大，然后終止訪問
{
num = INF;
return;
}
//標記當前點已經經過但是不知道可不可以走
vis[x][y] = -1;
++num;
//如果這個點是n
if (s[x][y] == 'N')
{//z為進來的方向
if (z == 0 || z == 3)
{//那么就出去往這兩個方向
F(x, y + 1, 0);
F(x - 1, y, 3);
}
else
{//那么就往這兩個方向走，
F(x, y - 1, 2);
F(x + 1, y, 1);
}
}
else
{//那么進來就是z了
if (z == 0 || z == 1)
{//如果z從10進來，就從01出去
F(x, y + 1, 0);
F(x + 1, y, 1);
}
else
{//否則就從23出去
F(x, y - 1, 2);
F(x - 1, y, 3);
}
}
//確實可以走，那么就把訪問點標記為可走
vis[x][y] = 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
memset(ans, 0x3f, sizeof ans);
for (int i = 1; i <= n; ++i)
{
memset(vis, 0, sizeof vis);
num = 0;
for (int j = 1; j <= m; ++j)
{//從四個角落才可以出發，判定四個角落是否滿足出發條件
if (s[i][j] == 'N')
F(i, j, 1);
else
F(i, j, 3);
//取當前最小值，因為多次訪問會出現有大小的情況
ans[i][j] = min(ans[i][j], num);
}
}
for (int i = 1; i <= n; ++i)
{
memset(vis, 0, sizeof vis);
num = 0;
for (int j = m; j; --j)
{
if (s[i][j] == 'N')
F(i, j, 3);
else
F(i, j, 1);
ans[i][j] = min(ans[i][j], num);
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf(j == m ? "%d\n" : "%d ", ans[i][j] >= INF ? -1 : ans[i][j] * 2);
//結果乘2為最終答案
//你龍老板永遠是你龍老板
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/238594.html
標籤：其他