第七屆“圖靈杯“NEUQ-ACM程式設計競賽（個人賽）題解

A~H題ak代碼(大部分抄的)

A題：
面周長，嗯跑模擬，奇偶，奇奇，偶偶，后面有時間可能會更新證明，咕咕咕，琛爹呂爹yyds！！！！！

D題：
1.初始點不一定是左上角
2.路徑是來回走
3.判斷是 != ‘*’ 而不是 == ‘.’
4.琛爹呂爹yyds！！！！！！！

E題：
m>6，怕就是2*s，這個分界具體也不好找，m>100反正穩得很，等待有緣人解惑，琛爹呂爹金爺yyds！！！！

原題鏈接

//A.溜圈圈：點一，線二，面周長 
#include<bits/stdc++.h>
using namespace std;
int main() 
{
	int t;
	cin >> t;
	while (t --) 
	{
		int m, n;
		cin >> m >> n;
		if (m >= n) swap(m, n);

		if (m == 1 && n == 1) cout << 1;
		else if (m == 1 && n > 1) cout << 2;
		else if (m > 1 && n > 1) cout << 2 * (m + n - 2);

		cout << endl;
	}
	return 0;
}

// B.Thursday out:前綴和，二分 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1000000007;
int q[maxn], sum[maxn];

int main() 
{
	int T;
	cin >> T;
	while (T --) 
	{
		int n, x;
		cin >> n >> x;
		for (int i = 1; i <= n; i ++) 
		{
			cin >> q[i];
			sum[i] = sum[i - 1] + q[i];
		}
		
		int ans = 0;
		for (int i = 1; i <= n; i ++) 
		{
			int l = i, r = n;
			while (l < r) 
			{
				int mid = l + r >> 1;
				if (sum[mid] - sum[i - 1] < x) l = mid + 1;
				else r = mid;
			}
			if (sum[r] - sum[i - 1] >= x) 
			{
				ans += n - r + 1;
				ans %= mod;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

//C:愛做筆記的Awen：string天下無敵！ 
#include <bits/stdc++.h>
using namespace std;

int n, cnt;
string ans, choose, add, temp;

int main() 
{
	cin >> n;
	while (n --) 
	{
		cin >> choose;
		if (choose == "Add") 
		{
			cin >> cnt >> add;
			ans += add;
		}
		if (choose == "Copy") 
		{
			temp = ans;
		}
		if (choose == "Del") 
		{
			cin >> cnt;
			ans.erase(ans.size() - cnt);
		}
		if (choose == "Paste") 
		{
			ans += temp;
		}
	}
	cout << ans << endl;
	return 0;
}

//D.Awen的一卡通：BFS
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 105;
int n, m, a, ans_x, ans_z;
char g[N][N];
int d[N][N];
int begin_x , begin_y ;

void bfs()
{
    queue<PII> q;

    memset(d, -1, sizeof d);
    d[begin_x][begin_y] = 0;
    q.push({begin_x, begin_y});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];

            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '*' && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }
    
    return;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
		cin >> g[i] ;  
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
        	if(g[i][j] == 's')
        	{
        		begin_x = i;
				begin_y = j; 
			}
		}    	
	}
	cin >> a;
	
    bfs();
    
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
        	if (g[i][j] == 'x') ans_x = d[i][j] * 2 + a;
			if (g[i][j] == 'z') ans_z = d[i][j] * 2 ;
		}    	
	}
	
    if (ans_x == ans_z) cout << "awennb";
    else if (ans_z < ans_x) cout << "wo tu le";
    else cout << "ying ying ying";
    
    return 0;
}

//E.Iris天下第一：貪心，dp背包，琛爹天下第一！
#include <bits/stdc++.h>
#define maxn 300005
#define ll long long
using namespace std;

int n , m , ans;

struct volume_value 
{
	int volume;
	int value;
};

bool cmp(volume_value x , volume_value y) 
{
	return x.value * y.volume < y.value * x.volume ;
}

int dp[maxn];
volume_value boy[maxn];

int main() 
{
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin >> boy[i].volume >> boy[i].value;
	}	
	
	sort(boy + 1, boy + 1 + n , cmp);
	while(m > 6 && n) 
	{
		m -= boy[n].volume;
		ans += boy[n].value;
		n -- ;
	}
	
	for(int i = 1; i <= n ; i ++)
	{
		for(int j = m; j >= boy[i].volume ;j--)
		{
			dp[j] = max(dp[j] , dp[j - boy[i].volume] + boy[i].value) ;
		}
	}
	
	int Max = 0 ;
	for(int i = 0 ; i <= m ; ++i)
	{
		Max = max(Max , dp[i]) ;
	}
	cout << Max + ans << endl ;
}

//F.我的夢想是世界和平:貪心O(1)過
#include <bits/stdc++.h>
using namespace std;

int t;
int a, b, c;
int a_room[3];

int main() 
{
	cin >> t;
	while (t --) 
	{
		cin >> a >> b >> c;
		if (c < a) swap(a, c);

		a_room[0] = c/2;
		a_room[1] = c - c/2;
		a_room[2] = a;

		sort(a_room, a_room + 3);

		if (a_room[2] * 3 < a + b + c) 
		{
			double a1 = a, b1 = b, c1 = c;
			cout << ceil((a1 + b1 + c1) / 3);
		} 
		else 
		{
			cout << a_room[2];
		}
		
		cout << endl;
	}
	return 0;
}

//G.跳格子：dp最長連續下降子序列 
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;

int a_steps[maxn], dp[maxn];
int n, ans;

int main() 
{
	cin >> n;
	for(int i = 0; i < n; i ++) 
	{
		cin >> a_steps[i];
	}
	
	for(int i = 1; i < n; i ++) 
	{
		if(a_steps[i - 1] > a_steps[i] ) 
		{
			dp[i] = dp[i - 1] + 1;
		}
	}
	
	for(int i = 0; i < n; i ++) 
	{
		ans = max(ans, dp[i]);
	}
	cout << ans;
	
	return 0;
}

//H.計分板：直接--好像會超時，改成++
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 300000 + 5;
ll a[maxn];

int main()
{
	ll n, k, q;
	cin >> n >> k >> q;
	
	for (ll i = 1; i <= q; i ++)
	{
		ll x;
		cin >> x;
		a[x] ++;
	}
	
	for (ll i = 1; i <= n; i ++)
	{		
		if (a[i] + k - q> 0) cout << "Yes" << ' ';
		else cout << "No" << ' ';
	}
	
	return 0;	
}