Sufferingcreatinglife

1705

WangJY
acwing_4510

77777777777

815741912
tianen
fangy
trudbot
AcWing2AK

Pluto1029
ech0_7
dugn2119

Eric.
tuffynibbles
cht
007_4

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
int res,ans;

void dfs(int k,int x)
{
if(k == n)
{
if(m - x >= ans) res ++ ;
return ;
}

for (int i = x; i <= m; i ++ )
{
if(ans + i >= m) return;
ans += i;
dfs(k + 1,i);
ans -= i;
}
}

int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

while(cin >> m >> n)
{
ans = res = 0;
dfs(1,0);
cout << res << endl;
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
LL s[N];
int stk[N];
int n;

int main()
{
int x;
int top = 0;
int res = 0;
cin >> n;

for(int i = 1;i <= n;i ++ )
{
cin >> x;
s[i] = s[i - 1] + x - 100;
}

stk[ ++ top] = 0;

for(int i = 1;i <= n;i ++ )
{
if(s[i] < s[stk[top]]) stk[ ++ top] = i;
else if(s[i] > s[stk[top]])
{
int l = 1,r = top;
while(l < r)
{
int mid = l + r >> 1;
if(s[stk[mid]] >= s[i]) l = mid + 1;
else r = mid;
}
res = max(res,i - stk[r]);
}
}

cout << res;
return 0;

}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<int> a;

int main()
{
cin >> n;
int m = 0,res = 1;

for(int i = 2;i * i <= n;i ++ )
{
if(n % i == 0)
{
int c = 0;
while(n % i == 0) n /= i,c ++ ;
res *= i;
a.push_back(c);
while(1 << m < c) m ++ ;
}
}

if(n > 1) {res *= n;a.push_back(1);}

for(auto x : a)
if(x < 1 << m)
{
m ++ ;
break;
}

cout << res << " " << m;
return 0;
}


### 思路，设立一个行程哈希表，一个左哈希表表示左边有到它的点，设立一个集合表示所有机场，遍历集合即可找出左边没有到它的机场为出发地，然后依次遍历行程哈希表，即可求出路径

#### 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<string,int> l;
unordered_map<string,string> s;
unordered_set<string> se;

int t,n;

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

cin >> t;
int len = t;
string x,y,start;

while(t -- )
{
l.clear(),s.clear(),se.clear();
cin >> n;
while(n -- )
{
cin >> x >> y;
l[y] ++ ;
s[x] = y;
se.insert(x);
se.insert(y);
}

for(auto & z : se)
if(!l[z])
{
start = z;
break;
}

cout << "Case #" << len - t << ": ";
while(s[start] != "")
{
cout << start << "-" << s[start];
if(s[start] != "") cout << " ";
start = s[start];
}
if(t != 0) cout << endl;
}

return 0;
}


### 思路，设立一个行程哈希表，一个左哈希表表示左边有到它的点，设立一个集合表示所有机场，遍历集合即可找出左边没有到它的机场为出发地，然后依次遍历行程哈希表，即可求出路径

#### 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<string,int> l;
unordered_map<string,string> s;
unordered_set<string> se;

int t,n;

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

cin >> t;
int len = t;
string x,y,start;

while(t -- )
{
l.clear(),s.clear(),se.clear();
cin >> n;
while(n -- )
{
cin >> x >> y;
l[y] ++ ;
s[x] = y;
se.insert(x);
se.insert(y);
}

for(auto & z : se)
if(!l[z])
{
start = z;
break;
}

cout << "Case #" << len - t << ": ";
while(s[start] != "")
{
cout << start << "-" << s[start];
if(s[start] != "") cout << " ";
start = s[start];
}
if(t != 0) cout << endl;
}

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N],b[N * 2] = {0};
int n;

int main()
{
int res = 0;
cin >> n;
for(int i = 0;i < n;i ++)  cin >> a[i],b[a[i]] = 1;

sort(a,a + n);

for(int i = 0;i < n - 1;i ++ )
if(a[i + 1] == a[i])
{

for(int j = a[i + 1] + 1;j < n * 2;j ++ )
if(!b[j])
{
//cout << j << " " << a[i + 1] << endl;
b[j] = 1;
res += j - a[i + 1];
break;
}
}

cout << res;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N],b[N] = {0};
int n;

int main()
{
string s;
cin >> n;
int c = 1,d = 1;
b[1] = 1;

while(d < n)
{
int e = d;
d = c + d;
c = e;
b[d] = 1;
}

for(int i = 1;i <= n;i ++ )
if(b[i]) s += string(1,'O');
else s += string(1,'o');

cout << s;
return 0;
}


#include <iostream>

using namespace std;

const int N = 21e5 + 10;
int n,m;
int a[N];

int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int res = 0,k,ans;
cin >> n;
int l = n;

while(n -- )
{
res = 0;
cin >> m;
for(int i = 0;i < m;i ++ ) cin >> a[i];
if(m == 1) printf("Case #%d: %d\n",l - n,1);
else
{
ans = 2;
k = a[1] - a[0];
for(int i = 1;i < m - 1;i ++ )
if(a[i + 1] - a[i] == k)
ans ++ ;
else
{
res = max(res,ans);
k = a[i + 1] - a[i];
ans = 2;
}
res = max(res,ans);
printf("Case #%d: %d\n",l - n,res);
}
}

return 0;
}


### 代码：

#include <iostream>

using namespace std;

const int N = 21e5 + 10;
int n,m;
int a[N];

int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int res = 0,k,ans;
cin >> n;
int l = n;

while(n -- )
{
res = 0;
cin >> m;
for(int i = 0;i < m;i ++ ) cin >> a[i];
if(m == 1) printf("Case #%d: %d\n",l - n,1);
else
{
ans = 2;
k = a[1] - a[0];
for(int i = 1;i < m - 1;i ++ )
if(a[i + 1] - a[i] == k)
ans ++ ;
else
{
res = max(res,ans);
k = a[i + 1] - a[i];
ans = 2;
}
res = max(res,ans);
printf("Case #%d: %d\n",l - n,res);
}
}

return 0;
}


#include <iostream>
#include <queue>
#include <unordered_map>

#define l first
#define r second

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
int a[N][N];
queue<PII> q;
int n,s;

int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);

int res,idx,ans,id;
cin >> n;
int k = 0;

while(n -- )
{
unordered_map<int,PII> mp;
int b[1000010] = {0};
idx = 1;
res = 0;
id = 0;
cin >> s;
for(int i = 0;i < s;i ++ )
for(int j = 0;j < s;j ++ )
{
cin >> a[i][j];
mp[a[i][j]] = {i,j};
}

while(idx <= s * s)
{
int start = idx;
ans = 0;
q.push(mp[idx]);

while(!q.empty())
{
PII x = q.front();
int dx = x.l,dy = x.r;
q.pop();
ans ++ ;
b[a[dx][dy]] = 1;
idx = max(idx,a[dx][dy]);
//if(i == 1 && j == 1) cout << dx << " " << dy << endl;
//cout << s << endl;

if(dx + 1 < s && !b[a[dx + 1][dy]] && (a[dx + 1][dy] == a[dx][dy] + 1))
q.push({dx + 1,dy});
if(dx - 1 >= 0 && !b[a[dx - 1][dy]] && (a[dx - 1][dy] == a[dx][dy] + 1))
q.push({dx - 1,dy});
if(dy + 1 < s && !b[a[dx][dy + 1]] && (a[dx][dy + 1] == a[dx][dy] + 1))
q.push({dx,dy + 1});
if(dy - 1 >= 0 && !b[a[dx][dy - 1]] && (a[dx][dy - 1] == a[dx][dy] + 1))
q.push({dx,dy - 1});
}
if(ans > res)
{
res = ans;
id = start;
}
idx += 1;
}

printf("Case #%d: %d %d\n",++ k,id,res);
}

return 0;
}